Photo by Ankush Minda on Unsplash

The need for higher kinds

You may have noticed that many kotlin-stdlib classes like and implement a function:

Some of the worst software engineering disasters arise from trying to achieve code reuse too soon. What if we tried to share ? If we did this, we could then write a function that consumed either a or a :

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 now have a return type of . If we call we lose the type information for , so we can’t go on to chain methods that would be available for a . Something like the following wouldn’t work as doesn't exist on :

We want to have an operation like 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 we encounter will have a method through polymorphism, whatever kotlin-stdlib collection we encounter, we can reasonably expect to find a 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 function for that does not care about the contents of the — it will handle just as well as .

With our multiple implementations of across different containers, aren’t we also obtaining a higher level of parametric polymorphism? When we write our containers like and , we imagine a ghostly “shape” for all of these containers. A shape that includes a function. If you know RxJava, think of how and etc. all implement 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 "?

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 (proper), and (first-order), but not (higher-order). We can parameterise, or abstract over, the choice of contents but not the choice of the container .

The red book

Recall that functions that take functions as parameters are called “higher-order functions.” Similarly, type constructors like that take other type constructors as parameters are called “higher-kinded type constructors.”

In this context, is a type constructor. To paraphrase the red book, there are no values of type but we can apply it to the type to produce . Likewise, we can apply the type constructor to the type constructor to get . 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 we instead write.

The containers we abstract over need to be represented using this . requires a type parameter, it’s not like the pre-generics version of collections classes like . We can’t write a type parameter of a type parameter, so something like is out of the question. Instead, we write a “witness” for called :

The first line is the class declaration, a simple class with no type parameters that can be applied to a . The second line is a “trick” to allow us to view as , moving the type parameters from being siblings in the to being applied one to the other.

The method is for transforming from higher back to first-order:

Since the boilerplate surrounding 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 function:

Now that we have a way of representing , we can now write a interface:

We can "tell” the compiler that conforms to the shape of in the following way:

Remember that is just an alias of . The “implementation” of ’s simply downcasts to (via ) and calls the pre-existing internal implementation of for . The downcast is safe as, by convention, we ensure that there is only one implementation of i.e., . This squares the circle for higher-kinded polymorphism in Kotlin: we can now abstract over a “container that implements .”

While our only has one function for now, we can imagine writing other functions on that take advantage of the critical function. This is in fact what happens in the arrow-core library. We used the name to make things easy, but the formal name for this concept is:

Signature for Functor (Mappable) including extension methods

The annotation causes these additional functions from to become available on as extension functions through code generated by the annotation processor. Since having enables other operations that, in turn, call , 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 :

Remember, is essentially the that we cannot normally represent using Kotlin. Because we abstract over , it is possible to substitute a different at the entry point to the application. For the standard implementation, we supply an that is the Arrow class :

However, we could easily swap this with another container. Imagine a requirement for interop with some pre-existing RxJava code. The RxJava class has a similar “shape” to in that it allows lazy execution of operations and failure with exceptions. We can substitute for at the entry points to the application:

This kind of deep change would be nearly impossible in traditional OO programming.

References

Arrow Glossary

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

Android

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store