Reducing type class boilerplate with Shapeless

Tweet about this on TwitterShare on LinkedInShare on FacebookShare on Google+Share on Reddit

If you followed our previous post on forging a DSL using type classes, you surely notice that writing type class instances is a rather repetitive task.

In today’s post we’re going to get rid of this by derivating type class instances automatically using Shapeless. We also use this post as an excuse to experiment with Shapeless and try to understand all the “magic” that’s happening.

To start with let’s get back to our finance DSL example. This is how we defined our currency amounts:

// The Amount type class
trait Amount[A] {
    def zero: A
    def plus(a: A, b: A): A
    def times(a: A, b: BigDecimal): A
  }
case class GBP(value: BigDecimal)
object GBP {
  // the Amount type class instance for GBP
  implicit object GBPIsAmount extends Amount[GBP] {
    override def zero: GBP = GBP(0)
    override def plus(a: GBP, b: GBP): GBP = GBP(a.value + b.value)
    override def times(a: GBP, b: BigDecimal): GBP = GBP(a.value * b)
  }
}
case class EUR(value: BigDecimal)
object EUR {
  // the amount type class instance for EUR
  implicit object EURIsAmount extends Amount[EUR] {
    override def zero: EUR = EUR(0)
    override def plus(a: EUR, b: EUR): EUR = EUR(a.value + b.value)
    override def times(a: EUR, b: BigDecimal): EUR = EUR(a.value * b)
  }
}

and if we want to add US dollars we would have

case class USD(value: BigDecimal)
object USD {
  // the amount type class instance for USD
  implicit object USDIsAmount extends Amount[USD] {
    override def zero: USD = USD(0)
    override def plus(a: USD, b: USD): USD = USD(a.value + b.value)
    override def times(a: USD, b: BigDecimal): USD = USD(a.value * b)
  }
}

And it goes on and on for every currency we want our DSL to support. You can see that writing type class instances adds lot of boilerplate code. Wouldn’t be nice if we could get rid of it and just define our amount classes as simply as that (without any boilerplate):

case class GBP(value: BigDecimal)
case class EUR(value: BigDecimal)
case class USD(value: BigDecimal)

Of course we still need to have our type class instances available somehow for our program to work. But we’d like to have them automatically generated for us.

So what do we need to be able to generate the type class instances automatically? Well, we need a way to create an instance of the appropriate case class and a way to access the underlying BigDecimal.

Let’s pause here for a moment because it may not be obvious how to do it (at least it wasn’t for me – at least without using reflection).

Let’s make a detour to generic programming here. I won’t try to give an exact definition of what generic programming is but I’ll rather try to give you a feeling of what it is.

To borrow an idea from Joe Barnes this is like entering a parallel world in Super Mario. Remember when Mario enters a warp pipe and lands into a sort of parallel world where everything looks the same but not quite.

In the normal world we have our regular case classes and we know how to deal with them. In the warp zone our case classes are replaced with some sort of “tuples” representing their fields.

case class GBP(value: BigDecimal)
// can be represented by
type genericGBP = (BigDecimal)

case class User(firstname: String, lastname: String, age: Int)
// can be represented by
type genericUser = (String, String, Int)

The case classes and the tuples are isomorphic: We can convert between them without loosing any information.

Interestingly all our different amount case classes turn into the same generic representation: (BigDecimal).
So it seems like we could define a type class instance for (BigDecimal) once and convert it back to the correct case classes.

That’s the idea! So let me introduce Shapeless’ Generic. Generic is like the pipes in Super Mario. It allows us to pass from one world to the other. There is one difference though: Shapeless doesn’t use tuples (which aren’t great to work with) but replace them with heterogenous list or HList for short.

An HList is a sort of mix between a tuple and a List. It can be thought of as a list where each element have it’s own type or as a tuple of variable length. Hopefully that’ll become clear when looking at some real code:

import shapeless.{ ::, Generic, HNil }
case class GBP(value: BigDecimal)
// HNil is the HList equivalent of Nil
val genericGBP: BigDecimal :: HNil = Generic[GBP].to(GBP(10))
val tenPounds: GBP = Generic[GBP].from(genericGBP) 

Pretty cool! It’s exactly what we need to derive type class instances for all our amount case classes.
Like pretty much everything in Shapeless Generic is a type class itself and is available via implicit resolution. Under the hood it uses a scala macro to do the conversion between HLists and the case classes.

First we’ll need a type class instance for the amount generic representation (BigDecimal :: HNil).
That’s pretty easy to write – it looks like any of the type class instance we wrote previously but we replace GBP with the type BigDecimal :: HNil.

object Amount {
  implicit val amountForBigDecimalHList: Amount[BigDecimal :: HNil] = 
    new Amount[BigDecimal :: HNil] {
      override def zero: BigDecimal :: HNil = BigDecimal(0) :: HNil
      override def plus(a: BigDecimal :: HNil, b: BigDecimal :: HNil): BigDecimal :: HNil = 
        (a.head + b.head) :: HNil
      override def times(a: BigDecimal :: HNil, b: BigDecimal): BigDecimal :: HNil = 
        (a.head * b) :: HNil
    }
}

Given this amountForBigDecimalHList we can now derive type class instances for every amount case classes using the appropriate Generic to convert between BigDecimal :: HNil to our case classes (e.g. GBP). We can get the correct Generic instance through implicit resolution – so that’s why we add it as an implicit parameter:

object Amount {
  ...
  implicit def genericAmount[A](
    implicit gen: Generic[A], amount: Amount[BigDecimal :: HNil]
  ): Amount[A] = new Amount[A] {
    override def zero: A = gen.from(amount.zero)
    override def plus(a: A, b: A): A = gen.from(amount.plus(gen.to(a), gen.to(b)))
    override def times(a: A, b: BigDecimal): A = gen.from(amount.times(gen.to(a), b))
  }
}

and … it doesn’t compile!

[error] ... type mismatch;
[error]  found   : shapeless.::[BigDecimal,shapeless.HNil]
[error]  required: gen.Repr
[error]       override def zero: A = gen.from(amount.zero)

To understand what’s happening let’s have a look at Generic. In fact it’s a pretty simple trait:

trait Generic[T] extends Serializable {
  type Repr
  def to(t: T): Repr
  def from(r: Repr): T
}

The thing is that Generic has a type instance Repr (which in our case is BigDecimal :: HNil). However we haven’t tell the compiler that Repr is actually BigDecimal :: HNil. This can be done with a weird syntax like this:

object Amount {
  ...
  implicit def genericAmount[A](
    implicit gen: Generic[A] { type Repr = BigDecimal :: HNil }, 
    amount: Amount[BigDecimal :: HNil]
  ): Amount[A] = new Amount[A] {
    override def zero: A = gen.from(amount.zero)
    override def plus(a: A, b: A): A = gen.from(amount.plus(gen.to(a), gen.to(b)))
    override def times(a: A, b: BigDecimal): A = gen.from(amount.times(gen.to(a), b))
  }
}

Now it compiles!

But does Repr have to be a BigDecimal :: HNil? Not necessarily it can be any type as long as we can find an Amount[Repr].(even though we only have an implicit for BigDecimal :: HNil so far).
Let’s rewrite genericAmount to be more generic (that will help us later on):

object Amount {
  ...
  implicit def genericAmount[A, R](
    implicit gen: Generic[A] { type Repr = R }, 
    amount: Amount[R]
  ): Amount[A] = new Amount[A] {
    override def zero: A = gen.from(amount.zero)
    override def plus(a: A, b: A): A = gen.from(amount.plus(gen.to(a), gen.to(b)))
    override def times(a: A, b: BigDecimal): A = gen.from(amount.times(gen.to(a), b))
  }
}

Specifying { type Repr = R } looks complicated. Fortunately Shapeless provides us with a nicer way to write the same thing using Generic.Aux

object Generic {
  type Aux[T, Repr0] = Generic[T] { type Repr = Repr0 }
}

which allows us to write our method signature like this

implicit def genericAmount[A, R](implicit gen: Generic.Aux[A, R], amount: Amount[R]): Amount[A]

With all this machinery set up we can now enjoy writing new currency amounts:

import Amount._
case class GBP(value: BigDecimal)
case class EUR(value: BigDecimal)
case class USD(value: BigDecimal)
val twentyPounds = GBP(15) + GBP(5)

That’s exactly what we wanted: no more boilerplate! All the type class instances are automatically available for us. Isn’t that nice? We have written all the machinery once and now we can support as many currencies as we like.

Great! Let’s move on. In the finance DSL we had another case class that was also an amount:

case class Per[A, B: Period](value: A, unit: B)

sealed trait Period[T] {
  def instance: T
}

This time the generic representation is different: A :: B :: HNil. For sure we can’t find an implicit type class instance with what we have done so far – but let’s look closer.

If A is an amount and if B is a period then we should be able to derive a type class instance for Per.

In fact the Period trait doesn’t really define anything specific to a period. The only thing it does is provide a way to create an instance out of nothing. Let’s rename it into DefaultInstance instead.

trait DefaultInstance[A] {
  def instance: A
}

Hmmm let’s get back to our generic representation: A :: B :: HNil. Basically it’s an HList and what can we do with HLists? We can recurse over them (like we do with lists).

import shapeless.{ ::, Generic, HList, HNil }
object DefaultInstance {
  // utility method to create a DefaultInstance[A]
  def apply[A](a: A): DefaultInstance[A] = 
    new DefaultInstance[A] { override def instance = a }
  
  // given a DefaultInstance for the head 
  // and a DefaultInstance for the tail
  // we can have a DefaultInstance for the whole list
  implicit def defaultInstanceForHList[H, T <: HList](
    implicit defaultHead: DefaultInstance[H], defaultTail: DefaultInstance[T]
  ): DefaultInstance[H :: T] = new DefaultInstance[H :: T] {
    override def instance: H :: T =
      defaultHead.instance :: defaultTail.instance
  }

  // Now we need a stop case: a DefaultInstance for HNil
  implicit val defaultInstanceForHNil: DefaultInstance[HNil] =
    new DefaultInstance[HNil] {
      override def instance: HNil = HNil
    } 
}

Good we can now have an implicit for B :: HNil (given there exists an implicit for DefaultInstance[B]).

The only missing piece is a way to generate an Amount type class instance for HLists. Once we have it it will plug nicely into the genericAmount[A, R] (where R is our HList).

implicit def amountForHList[H, T <: HList](
  implicit amount: Amount[H],
  defaultTail: DefaultInstance[T]
): Amount[H :: T] = new Amount[H :: T] {
  override def zero: H :: T = 
    amount.zero :: defaultTail.instance
  override def plus(a: H :: T, b: H :: T): H :: T = 
    amount.plus(a.head, b.head) :: defaultTail.instance
  override def times(a: H :: T, b: BigDecimal): H :: T = 
    amount.times(a.head, b) :: defaultTail.instance
}

Let’s see how all the pieces fit together! … Oh no, another compilation error:

diverging implicit expansion for type ShapelessDSL.Amount[this.Repr]

No worries, this is something common in Shapeless. Basically the compiler is over pessimistic when resolving the implicits and thinks that the expression it tries to resolve gets more and more complex so it stops and returns an error instead of keep going and find out that it works.

To get around it we need to use the Shapeless macro: Lazy (it wraps our type into a Lazy structure that is not evaluated at compile time).

import shapeless.{ ::, Generic, HList, HNil, Lazy }

implicit def amountForHList[H, T <: HList](
  implicit amount: Lazy[Amount[H]],
  defaultTail: DefaultInstance[T]
): Amount[H :: T] = new Amount[H :: T] {
  override def zero: H :: T = 
    amount.value.zero :: defaultTail.instance
  override def plus(a: H :: T, b: H :: T): H :: T = 
    amount.value.plus(a.head, b.head) :: defaultTail.instance
  override def times(a: H :: T, b: BigDecimal): H :: T = 
    amount.vallue.times(a.head, b) :: defaultTail.instance
}

Now let’s define the Year and Month period that we had in our previous post’s DSL:

object Period {
  sealed trait Month
  sealed trait Year
  final val Month = new Month() {}
  final val Year = new Year() {}
  implicit val defaultInstanceForMonth: DefaultInstance[Month] = DefaultInstance(Month)
  implicit val defaultInstanceForYear: DefaultInstance[Year] = DefaultInstance(Year)
}

… and we’re ready to have Per defined as amount.

import DefaultInstance._
import Period._
import Amount._

val twentyPoundsPerMonth = twentyPounds per Month
val fortyPoundsPerMonth = twentyPoundsPerMonth + twentyPoundsPerMonth

Let’s have some more fun and extend our DSL to support real estate. We certainly need to track prices per square meters.
Easy! We only have to define a SquareMeter instance like we did for Month and Year and we’re done.

object Surface {
  sealed trait SquareMeter
  final val SquareMeter = new SquareMeter {}
  implicit val defaultInstanceForSquareMeter: DefaultInstance[SquareMeter] = 
    DefaultInstance(SquareMeter)
}

import Surface._
val pricePerSquareMeter = EUR(1000) per SquareMeter
val expensiveSquareMeter = pricePerSquareMeter + (EUR(1200) per SquareMeter)

Do you want more? Let’s track the renting potential! Well that’s probably going to be expressed in Amount per square meter per Year. Guess what? It works out of the box! Not any boilerplate code to write:

val rentingPotential = USD(1800) per SquareMeter per Year
val estimatedCost = USD(1500) per SquareMeter per Year
val estimatedRevenue = rentingPotential - estimatedCost

Conclusion

That was just an introduction to Shapeless. As you can see generic programming is both a simple and powerful concept. All the implicit resolutions happen at compile time (which can increase substantially) but it also means that there almost no overhead at run time (except the conversion to/from HList – which is not too expensive).

Fixing compilation errors can be tedious as the compiler doesn’t really tell us which implicit resolution fails. (It may come useful to add the -Xlog-implicits scalac option).

As usual you can have a look at the source code used in this post on github and if you want to know more about Shapeless I highly recommend “The type astronaut’s guide to Shapeless” (free download).