Advanced FP for the Enterprise Bee: Higher Kinded Types

A Stack of Honeycomb

Introduction

This is the third in our series of articles, covering advanced FP concepts for the typical Kotlin developer. In the first article we showed how useful the traverse operator is. Along the way we encountered three unfamiliar concepts — Applicatives, Semigroups and Higher Kinded Types (HKT’s).

Our second article dealt with Applicatives and Semigroups. This article will complete the set by explaining Higher Kinded Types. We will start by revisiting the original problem, but then explain HKT’s from scratch.

As ever all the code for this series is available in this repository.

The Original Problem

Examine the code below. In particular think about the type of the parameters to functions output1, output2 and output3.

We see that data1 is the result of mapping over the range from one to five, generating a Right for each number. So presumably output1 can take some kind of List<Either>. This is indeed the case.

When we look at data2 we see that it is the result of traversing over an identical range. So we would expect the result to be some kind of Either<List>. Unfortunately, as the calls to fix suggest, this is not entirely the case.

Here are the matching functions:

If we call fix on both the list and its contents then we can call output2, passing in an Either<Int, List<Int>>. Without these magic incantations the actual type is baffling:

Kind<EitherPartialOf<Nothing>, Kind<ForListK, Int>>

Understanding what is going on here is one of the biggest barriers to learning Arrow, and befuddled me for a long time. So let’s pick our way through the concepts slowly.

A Simpler Example

Have a look at this, somewhat contrived, example.

We have a competition object that is going to judge whether an Either or a Validated object represents a winner or a loser. For an Either the Right case represents a winner, whereas for a Validated it is the Valid case.

Here’s the output produced:

winner
loser
winner
loser

Let’s assume that this kind of logic is important to the current application, so we decide to define an interface to represent the idea of a competition. See if you can work out what’s wrong with this attempt:

It makes logical sense. We declare our interface with three type parameters, and then give a method that takes a T of U and V. Sadly this will not compile. The problem is that in Kotlin, and most programming languages, it is not possible to nest type parameters.

Why This Matters

Using type parameters as arguments to a generic type is initially outlandish. It’s not something worker bees like us are going to do. But it turns out this is really important to designers of libraries built around FP.

As we have already seen a lot of FP is built around:

• Containers (Option, Either, Validated, Future, IO, etc…)
• Types that we place within containers (Customer, etc…)
• Operations on lists of containers of values (map, traverse, etc…)

Hence we want to define interfaces that represent the ‘shapes’ of these interactions. When explaining an FP shape like Applicative in English we might say something like:

“this operation applies to one or more T, where each T is a container holding either a U or a V”.

We want to be able to do the same in code. Which requires the ability to nest type parameters. Our inability to do this is a big problem when creating libraries like Arrow. In particular it prevents you creating something called Typeclasses. But that’s a topic for another article.

A Brief Digression To Scala

If we were writing this code in Scala then Higher Kinded Types would be available to us directly.

Here’s a Scala implementation of our Competition interface (aka. trait):

The most important point is this syntax:

Competition[T[_,_]]

It indicates that the Competition type requires a type parameter T, which in turn requires two type arguments of its own. In the implementations of judge we are then free to state that input is an Either[U, V] or Validated[U, V].

This is a good example of the differing value propositions of Kotlin and Scala. Kotlin provides as much FP as the typical developer requires, but not everything a library writer might desire. This keeps the language minimalist and the learning curve shallow.

Conversely Scala gives you all the features of both the FP and OO paradigms, on the assumption that you will combine them wisely. This means the possibilities are greater, but the learning curve is much steeper.

Given that we have hitched our pony to the Kotlin wagon, what can we use as a replacement for T[ _, _ ] ?

Solving the Problem in Kotlin

Here’s a solution to the problem in Kotlin. I present it below in full, so we can pick it apart incrementally:

As you can see our Competition interface takes a standard type parameter T, whilst the judge method takes U and V. So far so good, but we need to inform the compiler that U and V are nested within T.

The way this is done is via:

input: Kind2<T, U, V>

When we use the Kind types in Arrow we encode the fact that the first type parameter is a container for those that follow. We recursively nest Kind instances as required, using type aliases to simplify the naming.

Here’s the declarations from the Arrow source code:

interface Kind<out F, out A>
typealias Kind2<F, A, B> = Kind<Kind<F, A>, B>

At present the aliases go up to Kind22. Which seems like plenty.

What we are doing is replacing a hierarchical relationship with a compositional one. Kotlin doesn’t provide the former so we make do with the latter.

If you’re old enough this may ring a distant bell — it’s similar to the way we used to simulate inheritance in procedural languages back in the 90's. C and Visual Basic 6 were the most common examples. If that’s too retro for you, it’s also similar to how JavaScript emulates inheritance via prototype chaining.

When we implement the interface we replace the T type with what is referred to as a ‘witness object’. By convention the names of these objects begin with ‘For’. Hence we have ForEither and ForValidated.

Here are the matching declarations:

class ForEither private constructor() { companion object }
class ForValidated private constructor() { companion object }

As you can see these types are unremarkable. They exist only to be used as key values. The way they tie things together can be seen if we examine the declarations of our container types.

Here are the declarations for Either:

sealed class Either<out A, out B> : EitherOf<A, B> { ... }
typealias EitherOf<A, B> = arrow.Kind2<ForEither, A, B>
typealias EitherPartialOf<A> = arrow.Kind<ForEither, A>

Here are the declarations for Validated:

sealed class Validated<out E, out A> : ValidatedOf<E, A> { ... }
typealias ValidatedOf<E, A> = arrow.Kind2<ForValidated, E, A>
typealias ValidatedPartialOf<E> = arrow.Kind<ForValidated, E>

As you can see both Either and Validated inherit from Kind2, once we unpack the type alias. An Either extends Kind2<ForEither, A, B> whereas a Validated extends Kind2<ForValidated, A, B>. This is a pattern we could repeat with our own container types as necessary.

With this arrangement in place we are able to mimic Higher Kinded Types in Kotlin. Here’s a simple client to prove it works:

winner
loser
winner
loser

The Missing Element

If you’ve really been paying attention then you may have noticed I’ve left one step out. This being the numerous calls to fix that we had to insert manually.

Arrow will try to manage the conversion from Kind instances to the matching container when possible. But when this isn’t possible you call the fix method, which performs a runtime cast.

Here’s the definition for Either, as you can see it’s not complex:

@Suppress("UNCHECKED_CAST", "NOTHING_TO_INLINE")
inline fun <A, B> EitherOf<A, B>.fix(): Either<A, B> =
  this as Either<A, B>

Because the Either type extends from Kind2 the standard OO rules for sub-typing apply. When a Kind2 is expected, but an Either is provided, an upcast occurs automatically.

However when you have a reference of type Kind2, but an Either is expected, you must reassure the compiler that you are willing to take the risk of a downcast. This is typically done by invoking fix, but you could do it any other way you liked.

Conclusions

When I first started with Arrow I had no idea what was going on with HKT’s, and simply adopted the ‘Bob The Builder’ approach to compiler errors:

Slogan for Bob the Builder

But hopefully you now have a much better idea of what’s going on. To summarise what we have covered:

• Mainstream languages like Kotlin are optimised for regular developers, so they omit less useful features like the ability to nest type parameters.
• However these Higher Kinded Types are very useful for library writers trying to represent the common containers and operations used in FP.
• Fortunately there is a way to simulate this hierarchy of type parameters using composition. Most of the time this is not an inconvenience.
• However when browsing the Arrow documentation you will see frequent references to Kind instances. A Kind<A, B> is a replacement for A<B>.
• In Arrow container types like Either inherit from Kind. A limitation of the pattern is that occasionally you need to perform manual downcasts, typically via the fix method.

That’s all for now. Next time we will investigate the Kleisli.

References

You may find it helpful to have a look at:

• The description of these concepts in the Arrow Glossary
• This talk on ‘Higher Kinded Types in a Lower Kinded Language’
• The original paper on ‘Lightweight higher-kinded polymorphism’

Thanks

I am grateful to Richard Gibson and the Instil training team for reviews, comments and encouragement on this series of articles. All errors are of course my own.