This is shapeless' HList

sealed trait HList extends Product with Serializable

final case class ::[+H, +T <: HList](head : H, tail : T) extends HList {
  override def toString = head match {
    case _: ::[_, _] => "("+head+") :: "+tail.toString
    case _ => head+" :: "+tail.toString
  }
}

sealed trait HNil extends HList {
  def ::[H](h : H) = shapeless.::(h, this)
  override def toString = "HNil"
}

case object HNil extends HNil

The important thing to note is it is very similar to a standard scala List just at the type level. It has a head and tail as type parameters and the tail is itself an HList. The implementation details are not important for our purposes here. All we need to take from this is an HList is a recursive list (head, tail) which is either empty (HNil) or whose elements can be of different types.

A Type Level Operation on HList

This is a function defined in shapeless which helps client code work with HLists

trait Mapped[L <: HList, F[_]] extends Serializable {
  type Out <: HList
}
object Mapped {
  …
  type Aux[L <: HList, F[_], Out0 <: HList] =
    Mapped[L, F] { type Out = Out0 }
 implicit def hnilMapped[F[_]]: Aux[HNil, F, HNil] =
    new Mapped[HNil, F] { type Out = HNil }
  …
  implicit def hlistMapped1[
  H, T <: HList, F[_], OutM <: HList](implicit
  mt: Mapped.Aux[T, F, OutM]): Aux[H :: T, F, F[H] :: OutM] =
    new Mapped[H :: T, F] { type Out = F[H] :: OutM }
}

We can see all the parts we mentioned in the first post of this series. Recall:

Keywords
Input types
Output types
Body

Note there are multiple implicit def declarations. The modifiers implicit def are similar to case statements in value function bodies. Let's take this piece by piece.

The First Case

implicit def hnilMapped[F[_]]: Aux[HNil, F, HNil] =
new Mapped[HNil, F] { type Out = HNil }

When focusing on the types, the intent becomes clear

implicit def hnilMapped[F[_]]: Aux[HNil, F, HNil] =
  new Mapped[HNil, F] { type Out = HNil }

This reads something like: Given a type constructor, yield the empty HList. Simple enough! This stuff is comprehensible afterall!

The Second Case

implicit def hlistMapped1[
H, T <: HList, F[_], OutM <: HList](implicit
mt: Mapped.Aux[T, F, OutM]): Aux[H :: T, F, F[H] :: OutM] =
  new Mapped[H :: T, F] { type Out = F[H] :: OutM }

This is admittedly more complex. Let's take it in stride again focusing on the types.

implicit def hlistMapped1[
H, T <: HList, F[_], OutM <: HList](implicit
mt: Mapped.Aux[T, F, OutM]): Aux[H :: T, F, F[H] :: OutM] =
  new Mapped[H :: T, F] { type Out = F[H] :: OutM }

Given a head, a tail which is an HList, a type constructor and another HList
Also, given proof that this type class holds good for our tail
We can generate an HList where our type constructor is applied to our head and the tail follows

A brief Word on Induction

Many of the type level functions encountered in the wild are of this type. Where there is at the very least

a trivial case which produces some terminal element
a more complex case where given a type or arity n can produce a type of arity n+1

In other words, recursive types can be generated inductively assuming you have an instance of the recursive type and all the necessary parts to wrap that instance within the target type.

In the next post we'll create some type level code using these methods.

(Code on GitHub)

Shapeless is a library which makes generic programming in Scala easier. Generic Programming gives you the ability to build abstractions that the language does not directly support

First thing's first:

import shapeless._

For the purposes of this post, this is the only import needed.

HList

The HList type provides a way to maintain a collection of items whose types may be different. For example say you have an Int, a String and a Double that you want inside a list. Using a standard Scala List one has:

scala> List(1, "1", 1.0)
res0: List[Any]

The problem is the type information is lost, so when we use this data, we need to cast the appropriate index to the appropriate type. HList is a list which holds type information for each element separately. With the shapeless import, HLists are constructed using the :: operator

scala> 1 :: "1" :: 1.0 :: HNil//very similar syntax to standard List
res1: shapeless.::[Int,shapeless.::[String,shapeless.::[Double,shapeless.HNil]]]

We can see the type information for Int, String and Double are kept as part of the overall type. This implies we can produce concrete types for lists of arbitrary elements. This is the cornerstone of Generic Derivation with Shapeless.

Note: Yes, Scala has perfectly reasonable Product types with tuples and case classes and whatnot; however, for reasons that will become clear later in this post, these types are insufficient for our purposes here.

Typeclass Boilerplate

Let's take a typeclass

trait Foo[Type]{
  def bar(t: Type): String
}

Not super exciting but, it will get the point across. Say we create instances for Int, String and Double

implicit def fooInt = new Foo[Int]{
  def bar(t: Int): String = t + ": Int"
}
implicit def fooString = new Foo[String]{
  def bar(t: String): String = t + ": String"
}
implicit def fooDouble = new Foo[Double]{
  def bar(t: Double): String = t + ": Double"
}

Now we have instances we can use for all things that are Int or String or Double and we are happy with this for a time. Then we get a request for a Foo instance that can be used for both Int and String so, we produce one using our new friend the HList:

implicit def fooIntString = new Foo[Int :: String :: HNil]{
  def bar(t: Int :: String :: HNil): String = {
    val i :: s :: HNil = t //very similar syntax to standard List
    fooInt.bar(i) + ", " + fooString.bar(s)
  }
}

But, this is coming in from user input on a webservice and users are notoriously inconsistent with the ordering of their arguments. We need one for String then Int as well:

implicit def fooStringInt = new Foo[String :: Int :: HNil]{
  def bar(t: String :: Int :: HNil): String = {
    val s :: i :: HNil = t
    fooString.bar(s) + ", " + fooInt.bar(i)
  }
}

Great! But what about combinations with Double? And what about when we need to support Long or List[String] or any other type? The combinations here blow up quite quickly in any reasonable application. Luckily, Scala and Shapeless give us a few tricks to get rid of all the tedious boilerplate present in any typeclass polymorphic system.

Implicits to the Rescue

All of the typeclass definitions thus far have been declared implicit. There is a fantastic reason for this: Implicits get the Scala compiler to produce boilerplate declarations for us at compile time. We can greatly reduce the amount of boilerplate needed to create typeclass instances for combinations of types. All we have to do is tell the compiler what to do.

Recall, all our HList declarations end with HNil. We need an instance for HNil

implicit def fooNil = new Foo[HNil]{def bar(t: HNil): String = ""}

Recall too, what the type of our HList looked like

scala> 1 :: "1" :: 1.0 :: HNil
res1: shapeless.::[Int,shapeless.::[String,shapeless.::[Double,shapeless.HNil]]]

removing the noise, we can see a pattern of nesting: [Int,[String,[Double,HNil]]]. We know from math that when we have nested syntax, we evaluate from the inside out; this applies for Scala code as well. So logically, we start with an HNil, prepend a Double, prepend a String then prepend an Int.

We have given the compiler implicit typeclass instances for each of these types; all we need is to give it an implicit operation for prepending an instance onto another instance:

implicit def fooPrepend[Head, Tail<:HList](implicit
  head: Foo[Head],
  tail: Foo[Tail]): Foo[Head :: Tail] = new Foo[Head :: Tail]{
  def bar(t: Head :: Tail): String = {
    val hd :: tl = t
    head.bar(hd) + ", " + tail.bar(tl)
  }
}

This says, Given a Foo instance for some type, Head, and some HList, Tail, we can produce a new Foo instance for the HList, Head :: Tail. We can see this work in the REPL:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val a: Foo[Int :: HNil] = implicitly
val b: Foo[String :: HNil] = implicitly
val c: Foo[String :: Int :: HNil] = implicitly
val d: Foo[Double :: String :: Int :: HNil] = implicitly
val e: Foo[Double :: String :: Int :: String :: HNil] = implicitly

// Exiting paste mode, now interpreting.

a: Foo[shapeless.::[Int,shapeless.HNil]]
b: Foo[shapeless.::[String,shapeless.HNil]]
c: Foo[shapeless.::[String,shapeless.::[Int,shapeless.HNil]]]
d: Foo[shapeless.::[Double,shapeless.::[String,shapeless.::[Int,shapeless.HNil]]]]
e: Foo[shapeless.::[Double,shapeless.::[String,shapeless.::[Int,shapeless.::[String,shapeless.HNil]]]]]

There was no need to define by hand Foo instances for any HList type that is a combination of types for which implicit Foo instances exist in scope.

The Reason for HList

Why not just use any old Product type? HList, unlike Product, has a way to take any HList and combine it with another type to produce another HList. There is no such capability baked into Product.

Recall, the last thing we did was build a Foo instance for a larger HList out of a Foo instance for a smaller HList. This process, started with the smallest possible HList, HNil, and built larger and larger HLists until the required type was produced.

This talk of Products leads us to our next step. Most applications have a lot of Product types and need typeclass instances for these Products. Given an HList is just a really fancy Product can we generically derive instances for tuples and case classes?

Note: There is an excellent talk on how to do this with nested Tuples.

Generic

Shapeless provides a typeclass, Generic, which helps convert between Product and its similar (isomorphic) HList. It is fairly straight forward to produce a Generic instance for a Product and get an HList:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val gen = Generic[(Int, String)]
val asH = gen.to((1, "1"))

// Exiting paste mode, now interpreting.

gen: shapeless.Generic[(Int, String)]
asH: gen.Repr = 1 :: 1 :: HNil

With this, we can take any Product and create a Foo instance for an HList that is similar:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val genIS = Generic[(Int, String)]
val genDS = Generic[(Double, String)]
val a = implicitly[Foo[genIS.Repr]].bar(genIS.to(1, "1"))
val b = implicitly[Foo[genDS.Repr]].bar(genDS.to(1.0, "1"))

// Exiting paste mode, now interpreting.

genIS: shapeless.Generic[(Int, String)]
genDS: shapeless.Generic[(Double, String)]
a: String = 1: Int, 1: String
b: String = "1.0: Double, 1: String, "

This implies given:

a Product, P
a Generic instance for P, gen
and an implicit Foo instance for the HList, gen.Repr

We can produce a result that would be valid for an instance of Foo[P]. All we need to do is find a way to delegate the work Foo[P] needs to do to an instance of Foo[gen.Repr].

Generic Derivation

Like before, we'll use an implicit def so the compiler helps us along.

implicit def fooProduct[P<:Product, H<:HList](implicit
  gen: Generic[P]{type Repr = H},//compiler needs to know Generic converts P to H
  foo: Foo[H]): Foo[P] = {
  new Foo[P]{
  def bar(p: P): String = foo.bar(gen.to(p))
}
}

This states, Given a Product and an HList, P and H, a Generic instance, gen, which can convert between P and H and a Foo instance for H, we can construct a Foo instance for P. There are two things to note:

We do not need to type implicit instanced for Generic like we had to for Foo
The implicit Generic needs a structural bound

The shapeless library provides out of the box, automatic Generic instances for any Product type and brings these into implicit scope. The problem with Generic is the type Repr is a member (dependent) type not a type parameter. In order to make sure the compiler can prove Repr is indeed our parameter H, we need to give it explicitly. And with this, we have our generic derivation for Foo:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val f: Foo[(String, Int)] = implicitly
val g: Foo[(Double, String, Int)] = implicitly
val h: Foo[(Double, String, Int, String)] = implicitly

case class A(i1: Int, i2: Int, s: String)
case class B(d: Double, s: String)
case class C(i1: Int, d1: Double, s: String, d2: Double, i2: Int)
val i: Foo[A] = implicitly
val j: Foo[B] = implicitly
val k: Foo[C] = implicitly

// Exiting paste mode, now interpreting.

f: Foo[(String, Int)]
g: Foo[(Double, String, Int)]
h: Foo[(Double, String, Int, String)]
defined class A
defined class B
defined class C
i: Foo[A]
j: Foo[B]
k: Foo[C]

And that's that! We can derive instances for our type class for any Product given each individual type within the product has an implicit instance defined.

In Sum

Shapeless provides a framework for Generic Programming which can help us remove boilerplate from our applications and derive instances for types that would be too tedious to write out ourselves. To take advantage of the derivation one needs a few parts:

Implicit instances for basic types like Int, String, Double, etc...
An implicit instance for HNil
An implicit def which when given implicit instances for a type and an HList, Head and Tail, can produce an implicit instance for the HList, Head :: Tail.
An implicit def which for a Product, P, when given implicit instances for an HList, H, and a Generic which can convert between P and H, can produce an implicit instance for P