Higher Kinded Types

What is a kind? Link to heading

Kinds are to types what types are to values. They’re the “type” of types. The symbol used to denote a kind is generally *, though you sometimes see systems also use Type in place of *.

Here are some examples of types and their corresponding kinds:

• String is *

• IO is * -> *

• List is * -> *

• Option is * -> *

• Either is * -> * -> *

We would call List, Option, etc. type constructors because they take type parameters. List has one type parameter, Either has two type parameters.

Let’s fill out a couple type parameters and see what kinds we are left with:

• Option[String] is *

• Either[String, *] is * -> *

We can assign a value to a binding with a proper type ¹:

val someName: Option[String] = Some("potato")

What is a higher kinded type? Link to heading

All the types with kinds that have parenthesis somewhere on the left hand side are higher kinded types (HKTs). Some examples:

• Functor is (* -> *) -> * ²

• OptionT is (* -> *) -> * -> *

• EitherT is (* -> *) -> * -> * -> *

• FreeT is (* -> *) -> (* -> *) -> * -> *

We would still call these type constructors ³, but the difference is they actually take type constructors as arguments as well.

Again, let’s fill out some type parameters to see what we’re left with:

• Functor[Option] is *

• EitherT[IO, Throwable, Int] is *

• OptionT[IO, *] is * -> *

• FreeT[IO, *, Int] is (* -> *) -> *

we can still assign a value to a binding with a proper type:

implicit val functorOpt: Functor[Option] = ???

See how to implement in the Functors Example section

Functors Link to heading

Functor is a higher kinded type, we’ll take a closer look at it to get an idea of how HKTs play out in practice.

Here is the definition in Scala:

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(fn: A => B): F[B]

F[_] here is a type of kind * -> *. In Java, the closest you could get is this:

interface FakeFunctor<F> {
    <A, B> F map(F fa, Function<A, B> fn);
}

This isn’t a real functor though. Even if Java had HKTs, there are other issues ⁴.

Notice in the Scala, fa is typed as F[A], while in the Java it’s just F. This would mean we’d have no way to apply fn to fa in the implementation. Similarly, the result is F, while in Scala it’s F[B]. What we’d need is this:

interface Functor<F<_>> {
    <A, B> F<B> map(F<A> fa, Function<A, B> fn);
} 

Functors Example Link to heading

trait Functor[F[_]]:
    def fmap[A, B](fa: F[A])(fn: A => B): F[B]

given Functor[Option] = new Functor:
    def fmap[A, B](fa: Option[A])(fn: A => B) = fa.map(fn)

given Functor[List] = new Functor:
    def fmap[A, B](fa: List[A])(fn: A => B) = fa.map(fn)

extension [F[_]: Functor, A](fa: F[A])
    def fmap[B](fn: A => B) = summon[Functor[F]].fmap(fa)(fn)
  
    def mapIf[B](cond: A => Boolean)(fn: A => B): F[A | B] =
        fa.fmap(a => if cond(a) then fn(a) else a)

List.range(1, 6).mapIf(_ % 2 == 1)("odd " + _)
// value is List(odd 1, 2, odd 3, 4, odd 5)
// type is List[Int | String]

fmap was used as an alternative name to map to highlight when the functor’s fmap was being used vs. built in map functions on Option/List.

Givens/implicits allow instances ⁵ to be used ergonomically. In almost all codebases where you find Functors, they’re defined in a library or the stdlib, and a ton of instances are defined for you, so you rarely have to make your own. If we used the cats library (part of the typelevel ecosystem), we’d instead have:

import cats.*
import cats.syntax.all.*

extension [F[_]: Functor, A](fa: F[A])
    def mapIf[B](cond: A => Boolean)(fn: A => B): F[A | B] =
        fa.map(a => if cond(a) then fn(a) else a)

List.range(1, 6).mapIf(_ % 2 == 1)("odd " + _)

Higher Order Function analogy Link to heading

There’s a pretty clear analogy between higher order functions and higher kinded types, when we map our terminology between the value level to the type level.

• a value of type A is like a proper type of kind *

• a function of type A -> B is like a type constructor of kind * -> *

• a higher order function of type (A -> B) -> C is like a higher kinded type of kind (* -> *) -> *

we could even align the language to make the analogy more clear:

• proper value =:= proper type

• value constructor =:= type constructor

• higher order value constructor =:= higher order type constructor

Do kinds have a “type”? Link to heading

In some languages, yes, they’re called sorts. In languages like Haskell or Scala they’re more meta-concepts than something that developers interface with through the type system.

In the same way you can reason about kinds in Java, Rust, Swift, or Kotlin without the type system/compiler knowing about them, you could reason about sorts in Haskell/Scala.

There are languages that make sorts more concrete like Agda or Idris, though once you get to that point the type systems generally become polymorphic over all universes of types. This generally comes with mechanisms for making reasoning between levels or traversing between them easier, and can enable things like dependent types.

Benefits Link to heading

While you can benefit from using HKTs yourself, making functions more generic than otherwise possible, we’ve had decades of research towards utilizing features like HKTs in making more capable type systems.

If you’re interested in a concrete example of the usefulness of HKTs, check out some of the more general mechanisms for tracking effects in my article Effect Tracking (like monads, mtl or AEs).