Type-Level Programming in Scala, Part 6f: Deriving type class instances through HLists

While some parts of this series have not been directly practical (Project Euler #4 in the type system), HLists themselves are definitely practical. The new task engine in sbt 0.9 avoids needing a lot of boilerplate or using a preprocessor while preserving type safety by using HLists (and KLists, a heterogeneous list with a type constructor common to each cell to be discussed in part 8).

For this post, however, let’s look at how we might use HLists to reduce another category of boilerplate. This one is related to defining type class instances, especially ones that are built up for a data type. The examples use scala.Equiv. If you aren’t familiar with Equiv, it is a type class for equality:

trait Equiv[T] {
   def equiv(a: T, b: T): Boolean
}

An instance for Int might look like:

implicit def intEquiv: Equiv[Int] = new Equiv[Int] {
   def equiv(a: Int, b: Int) = a == b
}

For Tuple2, we build on the Equiv instances for its members:

implicit def pairEquiv[A,B](implicit a: Equiv[A], b: Equiv[B]): Equiv[ (A,B) ] =
   new Equiv[ (A,B) ] {
      def equiv(t1: (A,B), t2: (A,B)) =
         a.equiv( t1._1, t2._1) && b.equiv( t1._2, t2._2)
   }

We’d need to repeat this for each TupleN. That is a bit annoying, but not too bad. N is fixed to 22 in Scala, so we can generate them ahead of time once and be done with it. However, user classes present an obstacle. We’ll consider case classes in particular, since Scala focuses on generating methods for these. Obviously, users can create as many case classes as they want. You cannot write an Equiv in advance for all of these classes. Instead, for each case class, the user needs to do something like:

case class Example[A,B](a: A, b: Seq[B], c: Int)

implicit def exampleEquiv[A,B](implicit a: Equiv[A], b: Equiv[Seq[B]], c: Equiv[Int]): Equiv[ Example[A,B] ] =
   new Equiv[ Example[A,B]] {
      def equiv(e1: Example[A,B], e2: Example[A,B]) =
         a.equiv( e1.a, e2.a ) &&
         b.equiv( e1.b, e2.b ) &&
         c.equiv( e1.c, e2.c )
   }

This is strictly boilerplate, since we are not saying anything new. We are duplicating the logic for an Equiv for Tuple3. The Example class is basically Tuple3[A,Seq[B], Int] and HLists are capable of representing arbitrary length tuples. We could write functions to convert between a HLists and our case classes. If we then make instances of our type class for HCons and HNil and for any case class that provides a conversion to and from HLists, we can automatically derive type class instances for any case class.

We need help from the compiler to auto-generate the conversion function between a case class and HLists. A prototype of this is here. With this patch to the compiler, the companion object of a case class has implicit conversions to and from the appropriate HList type. For the Example class above, it is roughly equivalent to the following manual definition:

case class Example[A,B](a: A, b: Seq[B], c: Int)
object Example {

   implicit def toHList[A,B](e: Example[A,B]): A :+: Seq[B] :+: Int :+: HNil =
      e.a :+: e.b :+: c :+: HNil

   implicit def fromHList[A,B](hl: A :+: Seq[B] :+: Int :+: HNil): Example[A,B] = {
      val a :+: b :+: c :+: HNil = hl
      Example(a,b,c)
   }
}

Then, we implement Equiv for HList and for anything convertible to HList:

object EquivHList {
      // HNil === HNil
   implicit def equivHNil: Equiv[HNil] = new Equiv[HNil] {
      def equiv(a: HNil, b: HNil) = true
   }
      // given Equiv for the tail and the head,
      //   (h1 :: t1) === (h2 :: t2) when
      //   (h1 === h2) and (t1 === t2)
   implicit def equivHCons[H,T <: HList](implicit equivH: Equiv[H], equivT: Equiv[T]): Equiv[HCons[H,T]] =
      new Equiv[HCons[H,T]] {
         def equiv(a: HCons[H,T], b: HCons[H,T]) =
            equivH.equiv(a.head, b.head) && equivT.equiv(a.tail, b.tail)
      }

      // given:
      //   a type T that is convertible to an HList of type HL
      //   an Equiv instance for HL
      // we can produce an Equiv[T] by mapping T to HL and using Equiv[HL]
   implicit def equivHListable[T, HL <: HList](implicit toHList: T => HL, equivHL: Equiv[HL]): Equiv[T] =
      new Equiv[T] {
         def equiv(a: T, b: T) =
            equivHL.equiv(toHList(a), toHList(b))
      }
}

So, we need to write something like EquivHList for each type class for which we want to automatically generate instances for case classes. Once we do that, though, we can just do:

case class Example[A,B](a: A, b: Seq[B], c: Int)

object Test {
   assert( Example('a', Seq(1,2,3), 19) === Example('a', Seq(1,2,3), 19) )
   assert( Example('b', Seq(1,2,3), 1) !== Example('a', Seq(1,2,3), 1) )
}

This example assumes === and !== are provided by an implicit conversion like:

implicit def equivEq[A](a1: A)(implicit e: Equiv[A]) = new {
   def ===(a2: A) = e.equiv(a1, a2)
   def !==(a2: A) = !e.equiv(a1, a2)
}

Predef.conforms also has to be hidden. Otherwise, equivHListable diverges. It would be good to have a nice fix for this.

As a final comment, even without the compiler auto-generating the conversions, it could be less work to manually define the conversions to and from HLists for each case class than it would be to manually implement the type class. This is likely to be the case when you want to implement multiple type classes for a case class.

In the next and last section of this part, I’ll discuss some ways to make working with HLists easier in Scala.

2 thoughts on “Type-Level Programming in Scala, Part 6f: Deriving type class instances through HLists

  1. Will this approach render different case classes with the same parameter types equivalent? Perhaps you could wrap the generated HList in a structure that includes the class, too.

    In the same vein, you could generate encode the parameter name in the generated HList. The obvious solution would be to generated a HList of (String, A). Perhaps more interesting would be:


    trait BaseParam { val name: String }
    case class HCaseManifest[P <: HList](cls: Class[_], params: P)

    case class A(a: Int, b: String)

    object A {
    sealed abstract class Param extends BaseParam
    object Param {
    case object a extends Param { val name = "a" }
    case object b extends Param { val name = "b" }
    }
    implicit def toHList2(value: A) = HCaseManifest(classOf[A], (Param.a, value.a) :+: (Param.b, value.b) :+: HNil)
    }

    I’m not sure how to encode the type constraint that the P must be a HList containing elements (_ <: BaseParam, A).

    The idea is that if you wanted to use a custom equality for one parameter out of many, you could declare of import a suitable implicit keyed on (A.Param.a.type, String). However this is probably stepping into the realms of a full blown reflection library.

  2. You end up with Equiv[Example], so you’ll only be able to compare Examples to each other.

    I have thought about generating parameter names as well. Generating a single HList of (String, A) makes it a bit more cumbersome when you don’t care about the String, but making them separate is problematic as well.

    Actually, it gets messy once you move away from simple types with HLists. That is, you want to state that your HList consists of values of type (String, a), where a varies with each cell. Since Scala does not have rank-2 types, this means you need a new data type, which I call KList. It captures the common type constructor across all cells with a signature like KList[M[_], HL <: HList]. To encode (bp <: BaseParam, a), you'd need K2List[M[_,_], HLa <: HList, HLb <: HList] because you now have two type parameters per cell. Then you say, hey, maybe I can abstract over KNList and there goes your weekend!

    As long as a type is only used once, you can of course easily replace its Equiv implementation. It is a good question how to best substitute a single Equiv in general.

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