There is a limitation in Kotlin's types system—it doesn't support Higher-Kinded Types (HKT). Without getting too much into type theory, an HKT is a type that declares other generic values as type parameters:
class MyClass<T>() //Valid Kotlin code
class MyHigherKindedClass<K<T>>() //Not valid kotlin code
Lacking HKT is not great for Kotlin concerning functional programming, as many advanced functional constructs and patterns use them.
Arrow's solution to this problem is to simulate HKT through a technique called evidence-based HKTs.
Let's have a look at an Option<T> declaration:
package arrow.core
import arrow.higherkind
import java.util.*
/**
* Represents optional values. Instances of `Option`
* are either an instance of $some or the object $none.
*/
@higherkind
sealed class Option<out A> : OptionKind<A> {
//more code goes here
Option<A> is annotated with @higherkind which is similar to @lenses from our previous chapter; this annotation is used to generate code to support evidence-based HKTs. Option<A> extends from OptionKind<A>:
package arrow.core
class OptionHK private constructor()
typealias OptionKind<A> = arrow.HK<OptionHK, A>
@Suppress("UNCHECKED_CAST", "NOTHING_TO_INLINE")
inline fun <A> OptionKind<A>.ev(): Option<A> =
this as Option<A>
OptionKind<A> is a type alias for HK<OptionHK, A>, all this code is generated using the @higherkind annotation processor. OptionHK is an uninstanciable class that is used as a unique tag name for HK and OptionKind is a kind of intermediate representation of HKT. Option.monad().binding returns OptionKind<T>, that is why we need to call ev() at the end to return a proper Option<T>:
package arrow
interface HK<out F, out A>
typealias HK2<F, A, B> = HK<HK<F, A>, B>
typealias HK3<F, A, B, C> = HK<HK2<F, A, B>, C>
typealias HK4<F, A, B, C, D> = HK<HK3<F, A, B, C>, D>
typealias HK5<F, A, B, C, D, E> = HK<HK4<F, A, B, C, D>, E>
HK interface (short-hand for higher-kinded) is used to represent an HKT of arity one up to HK5 for arity 5. On HK<F, A>, F represents the type and A the generic parameter, so Option<Int> is OptionKind<Int> value which is HK<OptionHK, Int>.
Let's have a look now at Functor<F>:
package arrow.typeclasses
import arrow.*
@typeclass
interface Functor<F> : TC {
fun <A, B> map(fa: HK<F, A>, f: (A) -> B): HK<F, B>
}
Functor<F> extends TC, a marker interface and, as you can guess, it has a map function. The map function receives HK<F, A> as the first parameter and a lambda (A) -> B to transform the value of A into B and transform it into HK<F, B>.
Let's create our basic datatype Mappable that can provide instances for the Functor type class:
import arrow.higherkind
@higherkind
class Mappable<T>(val t: T) : MappableKind<T> {
fun <R> map(f: (T) -> R): Mappable<R> = Mappable(f(t))
override fun toString(): String = "Mappable(t=$t)"
companion object
}
Our class, Mappable<T> is annotated with @higherkind and extends MappableKind<T> and must have a companion object, it doesn't matter if is empty or not.
Now, we need to create our implementation of Functor<F>:
import arrow.instance
import arrow.typeclasses.Functor
@instance(Mappable::class)
interface MappableFunctorInstance : Functor<MappableHK> {
override fun <A, B> map(fa: MappableKind<A>, f: (A) -> B): Mappable<B> {
return fa.ev().map(f)
}
}
Our MappableFunctorInstance interface extends Functor<MappableHK> and is annotated with @instance(Mappable::class). Inside the map function, we use the first parameter, MappableKind<A> and use its map function.
The @instance annotation will generate an object extending the interface, MappableFunctorInstance. It will create an Mappable.Companion.functor() extension function to get the object implementing MappableFunctorInstance using Mappable.functor() (which is how we can use Option.monad()).
Another alternative is to let Arrow-derived instances automatically provided that your datatypes have the right functions:
import arrow.deriving
@higherkind
@deriving(Functor::class)
class DerivedMappable<T>(val t: T) : DerivedMappableKind<T> {
fun <R> map(f: (T) -> R): DerivedMappable<R> = DerivedMappable(f(t))
override fun toString(): String = "DerivedMappable(t=$t)"
companion object
}
The @deriving annotation will generate DerivedMappableFunctorInstance that normally you will write manually.
Now, we can create a generic function to use our Mappable functor:
import arrow.typeclasses.functor
inline fun <reified F> buildBicycle(mapper: HK<F, Int>,
noinline f: (Int) -> Bicycle,
FR: Functor<F> = functor()): HK<F, Bicycle> = FR.map(mapper, f)
The buildBicycle function will take as parameter any HK<F, Int> and apply the function f using its Functor implementation, returned by the function arrow.typeclasses.functor and returns HK<F, Bicycle>.
The function arrow.typeclass.functor resolves at runtime, instances that adhere to the Functor<MappableHK> requirement:
fun main(args: Array<String>) {
val mappable: Mappable<Bicycle> = buildBicycle(Mappable(3), ::Bicycle).ev()
println("mappable = $mappable") //Mappable(t=Bicycle(gears=3))
val option: Option<Bicycle> = buildBicycle(Some(2), ::Bicycle).ev()
println("option = $option") //Some(Bicycle(gears=2))
val none: Option<Bicycle> = buildBicycle(None, ::Bicycle).ev()
println("none = $none") //None
}
We can use buildBicycle with Mappeable<Int>, or any other HKT class such as Option<T>.
One problem with the Arrows approach to HKTs is that it must resolve its instances at runtime. This is because Kotlin does not have support for implicits or can solve type class instances at compile time, leaving Arrow with this only alternative until KEEP-87 is approved and included in the language:
@higherkind
class NotAFunctor<T>(val t: T) : NotAFunctorKind<T> {
fun <R> map(f: (T) -> R): NotAFunctor<R> = NotAFunctor(f(t))
override fun toString(): String = "NotAFunctor(t=$t)"
}
So, you can have an HKT that has a map function but without an instance of Functor can't be used, yet isn't a compilation error:
fun main(args: Array<String>) {
val not: NotAFunctor<Bicycle> = buildBicycle(NotAFunctor(4), ::Bicycle).ev()
println("not = $not")
}
Calling buildBicycle with a NotAFunctor<T> function compiles, but it will throw a ClassNotFoundException exception at runtime.
Now that we understand how Arrow's hierarchy works, we can cover other classes.