Higher kinds in Kotlin
The need for higher kinds
You may have noticed that many kotlin-stdlib classes like List and Sequence implement a map function:
Some of the worst software engineering disasters arise from trying to achieve code reuse too soon. What if we tried to share map? If we did this, we could then write a function that consumed either a Sequence or a List:
The classic way of doing this in object-oriented programming would be to extract a common interface or abstract class. But look what happens in the attempt below:
Both implementations of map now have a return type of Mappable. If we call List#map we lose the type information for List, so we can’t go on to chain methods that would be available for a List. Something like the following wouldn’t work as size doesn't exist on Mappable:
We want to have an operation like map work across a range of classes. To understand why, imagine if we had to learn a different operator for each different collection we wanted to transform with a mapper! Just as whatever subclass of List we encounter will have a contains method through polymorphism, whatever kotlin-stdlib collection we encounter, we can reasonably expect to find a map function.
In functional programming, we talk of “parametric polymorphism.” This is not polymorphism through subclassing, or through implementation of interfaces. Rather, it is the polymorphism we obtain through generics. With generics we can write a map function for List that does not care about the contents of the List — it will handle List<Int> just as well as List<String>.
With our multiple implementations of map across different containers, aren’t we also obtaining a higher level of parametric polymorphism? When we write our containers like List and Sequence, we imagine a ghostly “shape” for all of these containers. A shape that includes a map function. If you know RxJava, think of how Observable and Single etc. all implement map but don’t obtain this implementation from sharing a common super-class.
But what if we could make the compiler see what we see? What if we could make the compiler understand “a data type that implements map"?
Higher kinds in Scala
It turns out we can do something like this in Scala:
But if we try this in Kotlin, we run into a problem. If we sidestep some of the syntax errors, we get:
The compilation error says that we aren’t allowed type arguments for type parameters. In a way, we have run into a limitation of generics on the JVM — Java 5 generics are first-order. There are no generics of a higher kind. In other words, we can have String (proper), and Sequence<A> (first-order), but not Mappable<F<_>> (higher-order). We can parameterise, or abstract over, the choice of contents A but not the choice of the container F.
Recall that functions that take functions as parameters are called “higher-order functions.” Similarly, type constructors like Mappable that take other type constructors as parameters are called “higher-kinded type constructors.”
In this context, Sequence is a type constructor. To paraphrase the red book, there are no values of type Sequence but we can apply it to the type String to produce Sequence<String>. Likewise, we can apply the type constructor Sequence to the type constructor Mappable to get Mappable<Sequence<_>>. The Stack Overflow question below explains this in more detail:
Can we get around the compiler limitation somehow? In a famous paper called “Lightweight higher-kinded polymorphism” Jeremy Yallop and Leo White explain a way we can implement higher-kinded type constructors in a language that was not built for them.
Let’s apply the paper’s technique to Kotlin. Since we can’t write Mappable<F<A>>, we instead writeMappable<Kind<F, A>>.
The containers we abstract over need to be represented using this Kind. Option requires a type parameter, it’s not like the pre-generics version of collections classes like Hashtable. We can’t write a type parameter of a type parameter, so something like Mappable<Kind<Option<*>, A> is out of the question. Instead, we write a “witness” for Option called ForOption:
The first line is the class declaration, a simple class with no type parameters that can be applied to a Kind<F,A>. The second line is a “trick” to allow us to view Kind<ForOption, A> as OptionOf<A>, moving the type parameters from being siblings in the Kind to being applied one to the other.
The fix method is for transforming from higher back to first-order:
Since the boilerplate surroundingForOption would need to be generated every time we wanted to use higher-kinded type constructors, we can use an annotation processor to emit the code for the witness class, type alias, and the fix function:
Now that we have a way of representing F<Option<_>>, we can now write a Mappable interface:
We can "tell” the compiler that Option conforms to the shape of Mappable in the following way:
Remember that OptionOf<A> is just an alias of Kind<ForOption, A>. The “implementation” of Mappable’s map simply downcasts Kind<ForOption, A> to Option<A> (via fix) and calls the pre-existing internal implementation of map for Option<A>. The downcast is safe as, by convention, we ensure that there is only one implementation of Kind<ForOption, A> i.e., Option<A>. This squares the circle for higher-kinded polymorphism in Kotlin: we can now abstract over a “container that implements map.”
While our Mappable only has one function for now, we can imagine writing other functions on Mappable that take advantage of the critical map function. This is in fact what happens in the arrow-core library. We used the name Mappable to make things easy, but the formal name for this concept isFunctor:
The extension annotation causes these additional functions from Functor to become available on OptionOf<A> as extension functions through code generated by the annotation processor. Since having map enables other operations that, in turn, call map, this can greatly increase code reuse — telling the compiler that our container is mappable will allow these extra operations that might not be present in the contract of the container itself. All while preserving the precious type information that would otherwise be lost.
So what?
We’ve done a lot of work to allow higher-kinded type constructors in Kotlin. But what can we do now that we couldn’t previously? To answer this question, let’s take a look at the Arrow example for Android:
Notice how the key methods parameterise over a container F:
Remember, Kind<F, List<NewsItem>> is essentially the F<List<NewsItem>> that we cannot normally represent using Kotlin. Because we abstract over F, it is possible to substitute a different F at the entry point to the application. For the standard implementation, we supply an F that is the Arrow class IO:
However, we could easily swap this with another container. Imagine a requirement for interop with some pre-existing RxJava code. The RxJava class Single has a similar “shape” to IO in that it allows lazy execution of operations and failure with exceptions. We can substitute IO for Single at the entry points to the application:
This kind of deep change would be nearly impossible in traditional OO programming.
References
Higher-kinded Polymorphism: What is it, why you want it by David Raab
Higher-kinded Types in a Lower-Kinded Language by Jacob Bass
Simulating Higher-Kinded Types in Java by John McClean
How KEEP-87 & Typeclasses will change the way we write Kotlin by Sebastian Sellmair
