<img height="1" width="1" src="https://www.facebook.com/tr?id=&amp;ev=PageView &amp;noscript=1">

This is the second blog post of the "Type level programming in Scala" series. In the first part, we introduced the concept of Typeclasses. Today, we will introduce HLists, then use them derive instances for typeclasses in a recursive manner.

Lists vs Tuples

Typically, Lists are used to contain an arbitrary number of elements of the same type. Therefore, if we insisted on defining a list of different types, the compiler picks the common super type of the elements to be the type of the List.

val l = 1 :: "Hello" :: false :: Nil
// l: List[Any] = List(1, Hello, false)

// res0: Any = 1

The example above shows how the Scala compiler lost the type information of the first element of the list.

On the contrary, tuples are capable of retaining the type information of every element.

val t = (1, "Hello", false)
// t: (Int, String, Boolean) = (1,Hello,false)

// res1: Int = 1

However, one drawback is that we can't abstract over the number of elements (arity).

def addElement[A, B, C](x: Tuple3[A, B, C]): Tuple4[String, A, B, C] = 
  ("newElement", x._1, x._2, x._3)
// addElement: [A, B, C](x: (A, B, C))(String, A, B, C)

// res2: (String, Int, String, Boolean) = (newElement,1,Hello,false)

Each tuple size has its separate class with a different number of type params (one for every element). We can't pass a tuple of different size.

addElement((1, "Hello", false, 2.0))
// <console>:14: error: type mismatch;
//  found   : (Int, String, Boolean, Double)
//  required: (?, ?, ?)
//        addElement((1, "Hello", false, 2.0))
//                   ^

Unfortunately, there is no common super type that allows doing basic operations on tuples without losing type information (but ).

Enter: HList

HList is a feature in Shapeless, a library for type-level programming. To use it in your project, you need to add this line in your build.sbt file

libraryDependencies += "com.chuusai" %% "shapeless" % "2.3.2"

Then import shapeless in your Scala file(s).

import shapeless._

HList is best of the two worlds, it is heterogeneous like tuples, yet allows you to abstract over arity/length. It could be either an empty list HNil, or a cons ::[H, T] where H is the type of the head, and T is the type of the tail, which is another HList.

scala> val hl1 = "Hello" :: false :: HNil
hl1: String :: Boolean :: shapeless.HNil = Hello :: false :: HNil

scala> val hl2 = 2.0 :: hl1
hl2: Double :: String :: Boolean :: shapeless.HNil = 2.0 :: Hello :: false :: HNil

Here is how hl2 looks like:

2.0      ::
  "Hello"   ::
     false      HNil

Note that the structure consists of nested ::, each of them has its own H and T types. This allows us to retain the type information of every element in the hlist's type (like Double :: String :: Boolean :: HNil).

Now let's define a generic function that prepends an element to any hlist.

def addElement[L <: HList](l: L) = "newElement" :: l

Note that we must specify that L is a subtype of HList (using the <: symbol) to be able to use the :: operator.

// res4: String :: String :: Boolean :: shapeless.HNil = newElement :: Hello :: false :: HNil

// res5: String :: Double :: String :: Boolean :: shapeless.HNil = newElement :: 2.0 :: Hello :: false :: HNil

In the example above, we were able to define a single function that operates on HLists of different length, yet the compiler is still aware of each invocation's type signature, including the length as well as the type of every element!

If we wanted to define the return type of addElement explicitly, it would be:

def addElement[L <: HList](l: L): String :: L = 
  "newElement" :: l

Note that :: is also a type, so we can refer to the output type as String :: L.

Using HList to represent objects

A very common use case for HLists is to use them as a generic representation of objects.

case class Employee(name: String, age: Int)
// defined class Employee

Generic[Employee].to(new Employee("Foo", 42))
// res6: String :: Int :: shapeless.HNil = Foo :: 42 :: HNil

Generic is part of shapeless, that is implemented via macros to convert any object to a similar HList and vice versa.

Generic[Employee].from("Bar" :: 99 :: HNil)
// res7: Employee = Employee(Bar,99)

Note that if the HList doesn't "look like" the case class, i.e has different types or even different order, the code doesn't even compile, so no nasty runtime exceptions.

scala> Generic[Employee].from(99 :: "Bar" :: HNil)
<console>:18: error: type mismatch;
 found   : Int :: String :: shapeless.HNil
 required: String :: Int :: shapeless.HNil
       Generic[Employee].from(99 :: "Bar" :: HNil)

Back to typeclasses

Do you still remember our Comparator typeclass from the previous blog? Excellent, let's update it to compare two HLists!

trait Comparator[T] {
  def compare(o1: T, o2: T): Int

implicit val intComparator = new Comparator[Int] {
  override def compare(o1: Int, o2: Int): Int = o1.compareTo(o2)

implicit val stringComparator = new Comparator[String] {
  override def compare(o1: String, o2: String): Int = o1.compareTo(o2)

def compare[T](o1: T, o2: T)(implicit cmp: Comparator[T]) = 
  cmp.compare(o1, o2)

So far we're able to compare Ints and Strings

scala> compare("Foo", "Bar")
res12: Int = 4

scala> compare(42, 99)
res13: Int = -1

We aim to be able to compare two hlists similar to.

val hl1 = "Foo" :: 42 :: HNil
// hl1: String :: Int :: shapeless.HNil = Foo :: 42 :: HNil

val hl2 = "Foo" :: 99 :: HNil
// hl2: String :: Int :: shapeless.HNil = Foo :: 99 :: HNil

// compare(hl1, hl2) // doesn't compile yet


Recursion could be a common pattern when working with normal Scala Lists, for example

def foo(l: List[Int]) = l match {
  case head +: tail => // do something on head, then combine with foo(tail) 
  case Nil => // base case, terminate the recurssion by returning a simple value

Our Comparator for HLists is very similar to the pattern above, first we need a base case for empty HList.

implicit val hNilComparator = new Comparator[HNil] {
  override def compare(o1: HNil, o2: HNil): Int = 0 

If both objects are empty, meaning they are equal, then we return 0.
Now, let's build a recursive implementation for non-empty HLists.

Firstly, we need to be able to split an HList to head and tail. We can achieve this by defining two type parameters H for head and T for tail, then we can refer to the hlist as the type H :: T.

implicit def hConsComparator[H, T <: HList] = 
  new Comparator[H :: T] {
    override def compare(o1: H :: T, o2: H :: T): Int = ???

Since our hlist type is defined as H :: T, calling o1.head will always return the type H, and o2.tail will be T, we know this at compile time.

Secondly, we need to be able to compare the head of the hlist, we need to politely ask the compiler to find a Comparator[H] for us!

implicit def hConsComparator[H, T <: HList](
  implicit hCmp: Comparator[H]
) = 
  new Comparator[H :: T] {
    override def compare(o1: H :: T, o2: H :: T): Int = 
      hCmp.compare(o1.head, o2.head) match {
      case 0 => ??? // Tie .. maybe we compare the second element?
      case other => other

Note that our implicit def can only have implicit parameter list! Adding any non-implicit param lists will cause the compiler to skip our implicit def.

Finally, we need to be able to compare the tail of the hlist, in case we got two equal heads.

implicit def hConsComparator[H, T <: HList](
  hCmp: Comparator[H], 
  tCmp: Comparator[T]
) = new Comparator[H :: T] {
  override def compare(o1: H :: T, o2: H :: T): Int = 
    hCmp.compare(o1.head, o2.head) match {
      case 0 => tCmp.compare(o1.tail, o2.tail)
      case other => other

Now we can compare hlists!

compare(hl1, hl2)
// res15: Int = -1

Generic Typeclass Instance

Remember the Generic typeclass we used to convert Employee instance to a hlist? Since it is a typeclass too, the compiler could provide it implicitly allowing us to define an instance for any case class!

implicit def genericComparator[T, L <: HList](
  gen: Generic.Aux[T, L],
  lCmp: Comparator[L]
) = new Comparator[T] {
  override def compare(o1: T, o2: T): Int = 
    lCmp.compare(gen.to(o1), gen.to(o2))

Generic.Aux is a special alias to Generic, that also specifies the type of the HList as a type param. This way can ask the compiler to find an instance of Comparator the same hlist L. We will revisit the Aux thingy later in this series, but for now don't worry about it.

Now we have a working example, we can compare instances of any case class!

compare(new Employee("Foo", 42), new Employee("Bar", 99))
// res16: Int = 4

Wrapping up

One one hand, tuples are heterogeneous, they can contain elements of different types, but we can't abstract over arity. On the other hand, collections can abstract over their size, but all elements have to be of the same type.

HLists are tuples on steroids that allows abstracting over arity. They can be used to represent objects generically. Also, they are very powerful when combined with typeclasses, as they allow "Typeclass Induction", by defining the typeclass instances in a recursive manner.


I am giving a talk at on 18 September about "Validating SQL on the type level". I'll be showing that Scala's type system is capable of type checking SQL-like queries against a schema using nothing but the same type level programming concepts (without connecting to the database at compile-time, no cheating!).

No previous type-level programming experience needed to attend the talk, in fact by reading this blog post you gave yourself a bit of advantage ;)

'Till I meet you at Scala.world, I'll leave you with this teaser of what I am going to demo on stage there! teaser

Recent Posts

Posts by Topic

see all

Subscribe to Email Updates