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 post is literate Scala:

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