Cool Monday: HList and Shapeless

Java (programming language) (Photo credit: Wikipedia)

HList as in heterogenous lists. This means every element is of different type. Yeah sure, just list List<Object> in Java, but that is in no way typesafe. I want compiler to know the type of every element and stop me if I try to do something silly.

Linked lists to the rescue

So what's a linked list anyway? A sequence of nodes with pointers to next. And a nice implementation(still talking Java here) would be generic to allow type-safety for homogeneous lists. It turns out generic are solution for HLists too. Just introduce additional type parameter. Apocalisp has a great post on implementing them in Java. Here's just a factory method to see the gist

public static <E, L extends HList<L>> HCons<E, L> HCons(final E e, final L l) {
   return new HCons<E,L>(e, l);
}

Problem comes with instantiation.

final HConsInteger[], HNil>>> b =
      cons(4.0, cons("Bar", cons(new Integer[]{1, 2}, nil())));

Java requires A LOT of type annotation. It works but it's just painful and it doesn't pay off.

Type inference to the rescue

Type inference gets rid of this problem entirely. Let's implement whole working HList in scala.

abstract class HList[H,T<:HList[_,_]] {
  def head: H
  def tail: T
  def ::[A](a: A) = Hcons(a, this)
}

object HNil extends HList[Nothing, Nothing]{
  def head = throw new IllegalAccessException("head of empty hlist")
  def tail = throw new IllegalAccessException("tail of empty hlist")
}

case class Hcons[H,T<:HList[_,_]](private val hd: H, private val tl: T) extends HList[H, T]{
  def head = hd
  def tail = tl
}

So this list can be instantiated like this

scala> val myHList = 1 :: "hi" :: 2.0 :: HNil
myHList: Hcons[Int,HList[java.lang.String,HList[Double,HList[Nothing,Nothing]]]] = Hcons(1,Hcons(hi,Hcons(2.0,HNil$@dbb62c)))

And it just works. Scala compiler does all the heavy lifting with type annotations. This implementation bare bones and doesn't provide any useful methods(even random access!). Check out Miles Sabin's shapeless project for a useful implementation and much more. I provides indexing, map, fold, concatenation, type-safe casts, conversions to tuples(and abstracting over arities!) and back. And even conversions with case classes. Just click the link above and read the readme. It's awesome.

Related articles

• A better Java: Scala or Xtend?
• Is Java Dead or Invincible?
• Quicksort - the Easy Way