Higher-kinded types in Scala

Versions: Scala 2.12.1

Types and type-safety in Scala have a special privileged place. But this wide range of techniques to deal with them makes the language discovery more difficult. And at first glance one of difficult type-related concepts are higher-kinded types, covered in this post.

Tree sections are devoted to higher-kinded types. The first of them defines these types. The next one gives some use cases while the final one shows their use in the code.

Higher-kinded types definition

Before going directly into the topic of this post, let's recall some basics about types hierarchy in Scala. Traversing this hierarchy will lead us automatically to the higher-kinded types. In the beginning of it we've proper types, symbolized with *. An example of such types are: Int, Double, String, Long, BigInt... and much more. Further we encounter first-order types represented as * -> * or * -> * -> *. Among their examples we can distinguish List[Int] (the 1st symbol) or Pair[Int, Strig] (the 2nd symbol). As you can deduce, first-order types are the types created by taking other types. This concept is also known under the name of type constructors and we consider that the proper type (e.g. List[Int]) is constructed by applying a type argument (Int) on the type constructor (List).

Finally at the end of that hierarchy we retrieve higher-kinded types represented as (* -> *) -> *. Regarding this notation we can consider these types as the type constructors taking another types constructors. We can also consider them as the types abstracting over types which abstract over types. Complicated enough ? Let's see some examples. A most popular use case is Functor represented as:

trait Functor[List[_]] {
  // ...

As you can see in this example, the Functor abstracts over List which in its turn abstracts over any available type (to understand the underscore, take a look at the post about existential types).

Higher-kinded types uses

So one of the main advantages of higher-kinded types is the genericity. They enable the creation of very general abstractions that can be used in many other libraries. One of popular projects using higher-kinded types is Scalaz extending the core Scala library for functional programming. And after quick research we can find our functors and monads, defined unsurprisingly with higher-kinded types:

trait Monad[F[_]] extends Applicative[F] with Bind[F] {
  // ...
}

trait Functor[F[_]] extends InvariantFunctor[F] {
  // ...
}

In Scala library one of examples using higher-kinded types are *Like traits, as: scala.collection.IterableLike or scala.collection.TraversableLike. They're used as in the following snippet:

sealed class PriorityQueue[A](implicit val ord: Ordering[A])
   extends AbstractIterable[A]
   // ...
   with IterableLike[A, PriorityQueue[A]] {
  // ...
}

If we take a look at IterableLike trait we'll see some generic methods that, in above case, apply directly on the PriorityQueue:

trait IterableLike[+A, +Repr] // ... 
  override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = {
    val lo = math.max(from, 0)
    val elems = until - lo
    val b = newBuilder
    if (elems <= 0) b.result()
    else {
      b.sizeHintBounded(elems, this)
      var i = 0
      val it = iterator drop lo
      while (i < elems && it.hasNext) {
        b += it.next
        i += 1
      }
      b.result()
    }
  }

  override /*TraversableLike*/ def take(n: Int): Repr = {
    val b = newBuilder

    if (n <= 0) b.result()
    else {
      b.sizeHintBounded(n, this)
      var i = 0
      val it = iterator
      while (i < n && it.hasNext) {
        b += it.next
        i += 1
      }
      b.result()
    }
  }

As you can correctly deduce, slice and take methods will construct the representations of Repr type with different elements.

Higher-kinded types example

To see higher-kinded types in action, we'll use already quoted Scalaz library and IterableLike:

behavior of "higher-kinded types"

it should "slice map with the IterableLike#slice method" in {
  val indexedLetters = new scala.collection.mutable.HashMap[Int, String]()
  indexedLetters.put(1, "a")
  indexedLetters.put(2, "b")
  indexedLetters.put(3, "c")
  indexedLetters.put(4, "d")
  indexedLetters.put(5, "e")

  val slicedMap = indexedLetters.slice(0, 2)

  slicedMap should have size 2
  slicedMap should contain allOf((2, "b"), (5, "e"))
  slicedMap shouldBe a [scala.collection.mutable.HashMap[_, _]]
}

it should "show how does Scalaz's Functor work" in {
  // basically Functor is for all mappable things
  // in this example, to not confuse with native List's map function
  // we'll empty all values of the list with void() method
  val numbers = List(1, 2, 3)
  import scalaz.{Functor, _}
  import std.list._
  val listFunctor = Functor[List]

  val emptiedList = listFunctor.void(numbers)

  emptiedList should have size 3
  emptiedList should contain only(())
}

In this post we discovered higher-kinded types, i.e. types abstracting over types which in their turn abstract over other types. As shown it's a very practical manner to generate some generic code, exactly as in the case of *Like traits (IterableLike or TraversableLike). This types category can also be used to implement purely functional structures as functors or monads, both present in the Scalaz library tested in the last section.