HList in Scala

This is my first blog post about Scala, so be gentle in your criticism :).

I've been trying to implement a linked list of heterogeneously typed elements in Scala, similar to HList for Haskell. This data type can for example be used as a replacement for all the TupleX types in the Scala standard library. A simple implementation of the HList data type in Scala might look like this:

object HListTest {
  sealed trait HList

  final class HNil extends HList {
    def ::[T](v : T) = HCons(v, this)
  }

  val HNil = new HNil()

  final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
    def ::[T](v : T) = HCons(v, this)
  }

  type ::[H, T <: HList] = HCons[H, T]
}

A list of arbitrary length can now be created:

val list : Int :: String :: Boolean :: HNil = 10 :: "hello" :: true :: HNil

Fine, now let's try to implement something more advanced like the append function:

case class Appender[L1 <: HList, L2 <: HList, Result <: HList](fn : (L1, L2) => Result)
{
  def apply(l1 : L1, l2 : L2) = fn(l1, l2)
}

def append[L1 <: HList, L2 <: HList, Result <: HList](l1 : L1, l2 : L2)
  (implicit fn : Appender[L1, L2, Result]) : Result = fn(l1, l2)

Note that the return type of the append function depends on the argument types. To use the append function we must provide two implicit functions that create instances of the Appender class for appending to the empty list and to a cons list:

implicit def nilAppender[L <: HList] : Appender[HNil, L, L] =
  Appender((v : HNil, l : L) => l)

implicit def consAppender[H, T <: HList, L2 <: HList, R <: HList]
  (implicit fn : Appender[T, L2, R]) : Appender[HCons[H, T], L2, HCons[H, R]] =
  Appender[HCons[H, T], L2, HCons[H, R]]((l1 : HCons[H, T], l2 : L2) => HCons(l1.head, fn(l1.tail, l2)))

A simple test case:

append(HNil, HNil)

What? Compiler error, no implicit argument found? Closer examination of the error message indicates that the Scala compiler has bound the Result type parameter of the append function to Nothing, and then it tried to find an implicit matching this type. This will obviously not work. Explicitly passing the nilAppender works:

append(HNil, HNil)(nilAppender)

It seems the return type of a function can't be inferred from implicit arguments, we must be able to specify the return type of append only with the help of the non-implicit parameters. This is unfortunately an example where the Scala type inferer is not as powerful as the one in Haskell.

Game over? No, we have one more ace up our sleeve: abstract types. Let's declare the return type of the append function as an abstract type in the HList trait, and modify the append and implicit functions to use type projections:

sealed trait HList {
  type Append[L <: HList] <: HList
}

final class HNil extends HList {
  type Append[L <: HList] = L

  def ::[T](v : T) = HCons(v, this)
}

final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
  type Append[L <: HList] = HCons[H, T#Append[L]]

  def ::[T](v : T) = HCons(v, this)
}

def append[L1 <: HList, L2 <: HList](l1 : L1, l2 : L2)
  (implicit fn : Appender[L1, L2, L1#Append[L2]]) : L1#Append[L2] = fn(l1, l2)

implicit def nilAppender[L <: HList] : Appender[HNil, L, L] = 
  Appender((v : HNil, l : L) => l)

implicit def consAppender[H, T <: HList, L2 <: HList, R <: HList]
  (implicit fn : Appender[T, L2, T#Append[L2]]) : Appender[HCons[H, T], L2, HCons[H, T]#Append[L2]] =
  Appender[HCons[H, T], L2, HCons[H, T]#Append[L2]]((l1 : HCons[H, T], l2 : L2) => HCons(l1.head, fn(l1.tail, l2)))

Now the simple test case works:

append(HNil, HNil)

A more advanced test works as well:

append(true :: HNil, 10 :: HNil).tail.head * 3

Nice! Have we implemented a type safe append function for heterogeneous lists of arbitrary length? Unfortunately not:

append(true :: "hello" :: HNil, 10 :: HNil)

This will cause an "illegal cyclic reference" compiler error. A type path can't contain the same type declaration twice, even though it or the enclosing type has different type arguments. In this case the HCons#Append type will be recursively evaluated twice for the first list type.

I've filed an enhancement ticket to remove this restriction. Hopefully it will be implemented some time in the near future, so the full power of abstract types and type projections can be utilized. In fact, there are many more things that can be implemented if this restriction is removed, see C++ MPL and Boost for some examples.

So, this is the current state of my exploration of Scala's wonderful type system. Unfortunately, at the moment it seems like HList can't be fully implemented in Scala. I'm grateful for comments proving me wrong though :)