HList

The Heterogeneous List aka HList is a pretty well-known data structure in the functional / type programming world and is a very interesting topic to cover as it can teach us a lot about Scala’s type system in general. John A. De Goes recently used this concept to model an SQL language in a typesafe fashion and presented its work in a Spartan session.

The problem tackled by HLists is about storing elements of different types (that is heterogeneous elements) and retaining information about these types at the same time.

val xs = List("a string", true, 42)
// xs: List[Any] = List(a string, true, 42)

While being able to store heterogeneous elements, a homogeneous List does not keep track of their types. Instead, it falls back on the first common supertype (Any in this case):

val xs = List(
  "a string", // String  -> AnyRef -> Any
  true,       // Boolean -> AnyVal -> Any
  42          // Int     -> AnyVal -> Any
)
// AnyRef and AnyVal have one parent in common which is Any,
// therfore `xs` is a `List[Any]`

Ideally, we would like to track the type of each element, just like we would do with tuples:

val xs: (String, (Boolean, (Int, Unit))) = 
  ("a string", 
    (true, 
      (42, ())
    )
  )

We can tackle this problem by providing an appropriate data structure:

sealed trait HList
object HList {
  case object Empty                                extends HList
  case class Cons[A, B <: HList](head: A, tail: B) extends HList
}

Empty represents an HList with no elements while a Cons is a cell containing one element A along with a tail storing the rest of the HList. An HList can be then built like following:

val xs: HList =
  Cons("a string", 
    Cons(true, 
      Cons(42, Empty)
    )
  )

This approach solves the problem but the syntax remains very verbose. We can improve this by adding an operator designed to prepend an element to an HList:

object HList {
  // ...
  implicit class ops[A <: HList](xs: A) {
    def prepend[B](b: B): Cons[B, A] = Cons(b, xs)
  }
}
// ...
val xs = Empty
  .prepend(42)
  .prepend(true)
  .prepend("a string")

With ops, we tell the compiler that any A subtyping an HList provides a prepend operator designed to add a B in front of the list. This is a bit confusing however as one has to build an HList starting from its last element (Empty). Let’s leverage infix notation and right associativity to make this more user-friendly:

implicit class ops[A <: HList](a: A) {
  def :*:[B](b: B): Cons[B, A] = Cons(b, a)
}
//...
val xs: Cons[String, Cons[Boolean, Cons[Int, Empty.type]]] =
    "a string" :*: true :*: 42 :*: Empty

As you probably know, infix operators (that is single parameter operators) suffixed with a : are right associative. This allows us to flip the callee and the caller during a function call:

  class Foo(val j: Int) {
    def *:(i : Int): Foo = new Foo(i)
  }

  val foo: Foo = 43 *: (new Foo(42))

This trick simplifies the composition of an HList at the value-level but the type of xs is still very verbose.

val xs: Cons[String, Cons[Boolean, Cons[Int, Empty.type]]] =
    "a string" :*: true :*: 42 :*: Empty

So let’s try to do the same improvement at the type-level using some type aliases:

object HList {
  // This alias prevents writing Empty.type everywhere we 
  // need to refer to `Empty` at the type-level
  type Empty = Empty.type

  type :*:[A, B <: HList] = Cons[A, B]
  // ...
}
// ...
val xs: String :*: Boolean :*: Int :*: Empty =
    "a string" :*: true :*: 42 :*: Empty

Notice that infix operators work at the value-level but also at the type-level. Using this technique, the type of an HList is now very readable. What about extracting elements from an HList now? To achieve this, an Extractor could be used:

object :*: {
  def unapply[A, B <: HList](cons: Cons[A, B]): Option[(A, B)] =
    Some((cons.head, cons.tail))
}
// ...
val s :*: b :*: i :*: _ = 
  "a string" :*: true :*: 42 :*: Empty

So far, we focused mainly on prepending one element to an HList but what about concatenating two HLists? Before getting deeper, let’s look at the code so far:

sealed trait HList
object HList {

  type Empty              = Empty.type
  type :*:[A, B <: HList] = Cons[A, B]

  case object Empty                                extends HList
  case class Cons[A, B <: HList](head: A, tail: B) extends HList

  object :*: {
    def unapply[A, B <: HList](cons: Cons[A, B]): Option[(A, B)] =
      Some((cons.head, cons.tail))
  }

  implicit class ops[A <: HList](a: A) {
    def :*:[B](b: B): B :*: A = Cons(b, a)
  }

  val xs: String :*: Boolean :*: Int :*: Empty =
    "a string" :*: true :*: 42 :*: Empty
}

Concatenating two lists is less trivial but not too hard either. One approach is to think about the type returned by a function designed for this purpose:

sealed trait HList {
  def ++[That <: HList](that: That): ???
}

No matter the type being returned, we need it to be a subtype of HList. Therefore:

sealed trait HList {
  type Append <: HList
  def ++[That <: HList](that: That): Append
}

Append has to be a type member because it may change depending on the subtype of the HList. If you look closely however, you will see that this design is flawed. To convince ourselves, let’s look at what this would imply for Empty:

object HList {
  // ...
  case object Empty extends HList {
    override type Append = ???
    override def ++[That <: HList](that: That): Append = ???
  }
}

What should be the implementation of Append in Empty? To figure this out, let’s look at the problem from a value perspective. Appending a list to an empty list results in returning the list itself. Therefore ++ should be defined like follow:

override type Append = ???
override def ++[That <: HList](that: That): Append = that

But what type should Append refer to? To fix this issue, we need to look at Append as a type-level function. That is a function which given a type returns another one:

override type Append[That <: HList] = That
override def ++[That <: HList](that: That): Append[That] = that

Append[That <: HList] is a type-level function taking and returning a That, while ++ is a value-level function taking a value typed as a That and returning (once expanded) a That. In other words, there is a symmetry between Append[That <: HList] and ++, each living respectfully in the type-level world and the value-level world. We can now fix the definition of Append in HList:

sealed trait HList {
  type Append[That <: HList] <: HList
  def ++[That <: HList](that: That): Append[That]
}

Once this understood, implementing ++ in Cons is trivial:

case class Cons[A, B <: HList](head: A, tail: B) extends HList { self =>
  override type Append[That <: HList] = Cons[A, tail.Append[That]]

  override def ++[That <: HList](that: That): self.Append[That] =
    Cons(head, tail ++ that)
  // ...
}

Once again, notice the symmetry between the type level (tail.Append[That]) and the value level (tail ++ that). To give you a full picture, here’s the final code:

sealed trait HList {
  type Append[B <: HList] <: HList
  def ++[That <: HList](that: That): Append[That]
}
object HList {

  type :*:[A, B <: HList] = Cons[A, B]

  type Empty = Empty.type

  case object Empty extends HList {
    override type Append[B <: HList] = B

    override def ++[That <: HList](that: That): That = that
  }

  case class Cons[A, B <: HList](head: A, tail: B) extends HList { self =>
    override type Append[C <: HList] = Cons[A, tail.Append[C]]

    override def ++[That <: HList](that: That): self.Append[That] =
      Cons(head, tail ++ that)
  }

  object :*: {
    def unapply[A, B <: HList](cons: Cons[A, B]): Option[(A, B)] =
      Some((cons.head, cons.tail))
  }

  implicit class ops[A <: HList](a: A) {
    def :*:[B](b: B): B :*: A = Cons(b, a)
  }
}

and here’s how you can use it:

import HList._

val string :*: bool :*: int :*: _: String :*: Boolean :*: Int :*: Empty =
  "a string" :*: true :*: 42 :*: Empty


val x = "a string" :*: Empty
val y = 42 :*: Empty
  
val s :*: i :*: _ = x ++ y

The biggest takeaways of this exercise are first that we can get the same flexibility at the value and the type level, and secondly that thinking about types as functions can be a breakthrough when you tackle Type programming. However, the possibilities are not endless in Scala 2.x as there are cases when the compiler won’t be able to track types properly (especially when you start introducing GADTs) but are sufficient enough to provide correctness at the type level in most cases. The situation is vastly improved in Dotty.

I would like to thank John, Calvin and Adam for their mentoring and help to write this post.