Higher-kinded types in Scala

May 25, 2016

I was asked today to explain higher-kinded types, so I whipped up this little example in Scala.

Consider the following trait, which defines a functor:

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

Here, a functor abstracts over a generic type constructor F[_]. This is a type variable that itself abstracts over a type.

Because F[_] itself abstracts over a type, it is a so-called higher-kinded type. Its kind is represented as * -> *, which informally reads as "a function that, given a type, returns a type".

Familiar examples of this include generic collections, such as List[_], Array[_], Option[_], etc. These are all classes that, given a value type, construct a concrete collection type.

Let's put our functor to use. First, we need something shaped like F[_]. An Option-like data structure will do nicely:

sealed trait Choice[+A]
case class Yep[A](value: A) extends Choice[A]
case object Nope extends Choice[Nothing]

Choice is parameterized over A, and has two concrete implementations: Yep and Nope. Nothing is the bottom type in Scala, so a Choice[Nothing] is a subtype of any possible Choice[+A], since Choice[+A] is covariant in A.

Let's make a functor for Choice:

object ChoiceFunctor extends Functor[Choice] {
  def map[A,B](fa: Choice[A])(f: A => B): Choice[B] =
    fa match {
      case Nope   => Nope
      case Yep(a) => Yep(f(a))
    }
}

ChoiceFunctor implements a functor for Choice: when mapping a function f over a Choice, we either do nothing in the case of a Nope, or we construct a new Yep after applying f to the underlying value.

Let's try it out:

ChoiceFunctor.map(Yep(42))({ x => println(x) }) // 42

This article is literate Scala:

$ scodedown https://earldouglas.com/posts/higher-kinded.md
42