Higher Kinded Types

Higher kinded types are types which take types which take types as parameters. I know, it burns the eyes just to read that sentence. So let's try to break it down.

A type which takes a type is something we've already dealt with in a prior post. This is, for example, List or Option. Another name for these is type constructors. You can think of them as being similar to a constructor at the value level. At the value level, a constructor is a function which takes in values and returns a value of a new type. A type constructor, on the other hand, takes in another type (or types) and returns a new type. So what then is a type which takes a type which takes a type. Well, it's a higher kinded type or a type which takes a type constructor as a parameter. In Scala, these are defined as follows:

trait MyTrait[F[_]] {}

Here we have created a higher kinded type called MyTrait which takes in a single generic type parameter. This looks different from the type parameters we explored in a previous post in that it has an extra [_] on it. This syntax tells the Scala compiler that the generic type F is a type constructor. So MyTrait essentially wants to abstract over a type that abstracts over a type.

I’ve written the word "type" too many times already, so let's look at a real example that abstracts over the map function (as used in List and Option) using a higher kinded type class called Mappable.

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

This type class has a single function, map which takes two parameters. fa: F[A] is the value that we are applying the function f to. For example, F[A] could be a List[String] or an Option[Int]. The map function returns an F[B] meaning that all the elements inside F have been transformed from values of type A to values of type B.

Now let's create instances of this type class for List and Option.

object Mappable {

  implicit def apply[F[_]](implicit m: Mappable[F]): m.type = m

  implicit val mapList: Mappable[List] = new Mappable[List] {
    def map[A, B](fa: List[A])(f: A => B): List[B] =
      fa.map(f)
  }
  
  implicit val mapOption: Mappable[Option] = new Mappable[Option] {
    def map[A, B](fa: Option[A])(f: A => B): Option[B] =
      fa.map(f)
  }

}

Now we can create a method that uses our type class, and we can then call that method on both List and Option types.

def stringifyElements[F[_]: Mappable](fa: F[Int]): F[String] =
  Mappable[F].map(fa)(_.toString)
  
stringifyElements(Some(123)) // Some("123")
stringifyElements(List(1, 2, 3)) // List("1", "2", "3")

This function can operate on any F that has an instance of Mappable defined, which is nice since our implementation is highly portable and not tightly coupled to any specific type. This allows usage across many use cases and is especially helpful when you are creating a framework/library. When a library provides functions that abstract over types (and higher kinded types) it allows users to make the library code work with their own types, whatever they may be. The type class pattern, with type constraints, with higher kinded types, is very useful.

Multiple Types in Type Constructors

As you start working with higher kinded types, you may notice that some types don't quite fit the pattern we described above. For example, you'll notice that Map takes two type parameters, one for the key and one for the value type of the Map. When this is the case for a type, there are a few options for abstracting over it with higher kinded types.

1. Pinning one of the type parameters with a type alias.

type StringMap[V] = Map[String, V]

implicit val mapStringMap: Mappable[StringMap] = new Mappable[StringMap] {
  def map[A, B](fa: StringMap[A])(f: A => B): StringMap[B] =
    fa.map { case (k, v) => k -> f(v) }
}

Here we have created a new type alias called StringMap which makes it so there is only a single generic type in Map rather than multiple. From there, we can treat StringMap just like we would a List or Option.

1. Using a type lambda

implicit def mapMap[K]: Mappable[Map[K, *]] = new Mappable[Map[K, *]] {
  def map[A, B](fa: Map[K, A])(f: A => B): Map[K, B] =
    fa.map { case (k, v) => k -> f(v) }
}

We are not going to get too into type lambdas at this point, but basically the * character syntax above is telling the compiler where the "hole" should be for the higher kinded type. This syntax is equivalent to the StringMap approach above, but it doesn't pin the type for the key to String and instead lets it be any type. It is essentially a way to tell the compiler which of the types in the Map we are interested in abstracting over for the Mappable implementation.

It is worth noting that some higher kinded types allow having two "holes" or, in other words, take in type constructors which take in two types as parameters. Here we will define a new type class to show what this might look like.

trait Bimappable[F[_, _]] {
  def bimap[A, B, C, D](f: F[A, B])(fa: A => C)(fb: B => D): F[C, D]
}

Here we have defined a type class Bimappable which has a function called bimap. bimap allows passing two separate functions, one that modifies the key and one that modifies the value of each entry. We aren't going to implement this type class for Map, but an example usage would be:

val map = Map[Int, Int](1 -> 2)

Bimappable[Map].bimap(map)(_.toString)(_.toLong) // Map[String, Long]("1" -> 2L)

Note: The Mappable type class that we defined above is typically called Functor. You will see it referred to as this in, for example, the cats library, which is very commonly used for functional programming in Scala. Cats also provides a Bifunctor type class, which is what we implemented above as Bimappable.

Formal Terminology

It is important to know the formal terminology that is used when discussing types and higher kinded types as you will encounter it in various places on the internet. Here are some common terms and definitions.

• Types such as String or Int are referred to as zero order types or proper types. They are denoted by a single *.
• Types such as List or Option are referred to as first order types or type constructors and are denoted as * -> * meaning they are types which take a single type parameter. Notice that this notation is similar to how we would define a value-level constructor as a function which takes a value and returns another value (e.g., String => Name).
• Types such as Map or Either are referred to as first order types as well, but they have multiple type parameters. They are usually denoted as * -> * -> * or (*, *) -> *.
• Types such as Functor which are referred to as second order, or higher kinded types which are denoted as (* -> *) -> * meaning that they are types which take first order types.

Here are some examples using the types from this post:

• Mappable: (* -> *) -> * or higher kinded
• Bimappable: (* -> * -> *) -> * or higher kinded, but takes in types that have two type parameters rather than one.

The Scala repl (version 2.13.x) can confirm the "kind" of types for us:

scala> trait Functor[F[_]]
trait Functor

scala> :kind -v Functor
Functor's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

scala> trait Bifunctor[F[_, _]]
trait Bifunctor

scala> :kind -v Bifunctor
Bifunctor's kind is X[F[A1,A2]]
(* -> * -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

So what about third order types? These are types which take types which take type constructors and are denoted as ‌((* -> *) -> *) -> *. We actually refer to these as higher kinded types as well. Anything over a first order type is typically called higher kinded. Anything more than second order types are quite uncommon, but can still be useful in some scenarios.

Summary

• Type constructors are types which take other types as parameters.
• Higher kinded types abstract over the behavior of type constructors.
• We can define higher-kinded type classes, such as Functor, which define certain behaviors for type constructors. These type classes allow implementations to use generic type constructors (F[_]) while still being able to perform needed actions on F.