Type-Level Programming in Scala, Part 6a: Heterogeneous List Basics

An HList is an arbitrary-length tuple. The advantages of an HList over the TupleX classes in the Scala standard library are that we are (in theory) not restricted to a fixed length and we do not need to duplicate methods for each tuple arity. We can (somewhat) easily move between lengths by concatenating tuples or selecting a slice from a tuple. The disadvantages are that we lose the special syntax for tuple construction and types, such as (Int, Boolean) and (3, true), we sometimes run into limitations of the compiler or language, and some useful operations require complicated types.

HLists have been previously demonstrated in Scala (and even in Java). The Scala implementation there used a mix of type members on the HList hierarchy and type class like implicits.

Here we implement four basic operations that let us implement the other operations outside of the HList hierarchy and without a type class for each operation. These basic operations are prepend, fold left, fold right, and a “stuck zipper”. By stuck zipper, I mean a structure that points to a position in the HList and provides the HList before and after that position but cannot move left or right.

With these four operations, we can define:

  • Using folds: length, append, reverse, reverse append, last
  • Using ‘stuck zipper': at (select by index), drop, take, replace, remove, map/flatMap at a single index, insert, insert hlist, splitAt

With some extra type-classes, we will also define:

  • zip
  • heterogenous apply (apply an HList of functions to an HList of inputs)

To start, a very basic HList looks like:

sealed trait HList

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

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

// aliases for building HList types and for pattern matching
object HList {
  type ::[H, T <: HList] = HCons
  val :: = HCons
}

This basic definition is already useful. For example, the following shows type-safe construction and extraction:

  // construct an HList similar to the Tuple3 ("str", true, 1.0)
  val x = "str" :: true :: 1.0 :: HNil

  // get the components by calling head/tail
  val s: String = x.head
  val b: Boolean = x.tail.head
  val d: Double = x.tail.tail.head
    // compile error
  //val e = x.tail.tail.tail.head

  // or, decompose with a pattern match

  val f: (String :: Boolean :: Double :: HNil) => String = {
    case "s" :: false :: _ => "test"
    case h :: true :: 1.0 :: HNil => h
      // compilation error because of individual type mismatches and length mismatch
      // case 3 :: "i" :: HNil => "invalid"
    case _ => error("unknown")
  }

Note that we are using :: for HLists, although :+: or another name might be better in practice to distinguish it from the :: used for List concatentation and matching.

Next, we’ll define fold left and right, which we can use to easily implement append, reverse, length, and last.

About these ads

4 thoughts on “Type-Level Programming in Scala, Part 6a: Heterogeneous List Basics

  1. Two minor things with the HList implementation:
    1. Is there a reason why you don’t implement the duplicate :: methods (lines 4 and 8) once only in the HList trait?
    2. Scalac 2.8.0 appears to require a type annotation for HCons on line 13, ie … = HCons[H, T]

    I’m still catching up with the entire series, so sorry if the first question is answered later.

  2. 1. Although the two definitions look identical, the inferred return type is different. You have to introduce a This type member or parameter on HList and this gets complicated quickly. The better solution is to put it in a type class (see HListOps in the github code), which works most of the time, but not enough to remove :: from HCons/HNil.
    2. Yup, looks like it got eaten.

  3. example code doesn’t compile in Scala 2.8.1.RC4, there is no HNil object and HList is not imported. i’ve fixed it by adding following lines in the beginning:

    object HNil extends HNil
    import HList._

  4. Thanks for a great post! :)

    Alexander is right in that an instance of HNil in not defined. You could simply define it within the HList object:

    object HList {

    val HNil = new HNil
    }

    and import Hlist._ as mentioned.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s