Type-Level Programming in Scala, Part 8c: KList ZipWith

One use of KList and the ‘transform’ and ‘down’ methods from 8b is to implement methods like ‘zipWith’ for arbitrary tuple lengths. To start with, the signature of zipWith for a pair of Streams, operating on a fixed arity of 2, looks like:

def zipWith2[A,B,C](t2: (Stream[A], Stream[B]))(f: (A,B) => C): Stream[C] =
   t2 match
   {
      case (ha #:: ta, hb #:: tb) => Stream.cons( f(ha, hb), zipWith2( (ta, tb) )(f) )
      case _ => Stream.empty
   }

Example usage:

val nats = Stream.from(1)
val random = Stream.continually( math.random )
val seq = zipWith2( (nats, random) ) { (n, r) => if(r > 0.3) n else -n }

scala> seq.take(10).toList
res0: List[Int] = List(-1, 2, 3, 4, 5, 6, -7, -8, 9, 10)

For the implementation of zipWith2, if either Stream in the pair is empty, the resulting Stream is empty. Otherwise, there is a head element for each stream in the pair. We apply the provided function to these elements and make the result the head of a new Stream. The tail of this new Stream will be the result of recursing on the tails of the input pair.

To generalize this to arbitrary arity, we will operate on a KList of Streams. Because we want to abstract over arity, we use a heterogeneous list. We use KList instead of HList because we want to constrain each element in the tuple to be a Stream and we don’t care what the specific types of Streams the elements are, but we do want to preserve those types. When we take the head element of each Stream, the resulting list is the underlying HList type of the input KList. For example, given an input of type KList[Stream, A :: B :: HNil], when we take the head of each Stream in the KList we will get an HList of type A :: B :: HNil. This is like going from (Stream[A], Stream[B]) to (A,B).

So, if we end up with the underlying HList type, the function we will apply to the input KList must be a function from that HList type to some other type. In the example above, the function type would be A :: B :: HNil => T for some type T, which will be the type of the output Stream. With this, we have our signature for a generalized zipWith:

def zipWith[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Stream[T]

To implement this function, we again break the problem into two parts. If any Stream is empty, the resulting stream is empty. Otherwise, we get all the head elements of the Streams as an HList, apply the input function to it, and make this the new head. For the tail, we get all of the tails of the Streams and recurse. To get the head elements, we use ‘down’ because we want KList[Stream, HL] => HL. For the tails, we use 'transform' because we need a mapping KList[Stream, HL] => KList[Stream, HL]. The implementation looks like:

def zipWith[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Stream[T] =
   if(anyEmpty(kl))
      Stream.empty
   else
      Stream.cons( f( kl down heads ), zipWith(kl transform tails )( f ) )

def anyEmpty(kl: KList[Stream, _]): Boolean = kl.toList.exists(_.isEmpty)

val heads = new (Stream ~> Id) { def apply[T](s: Stream[T]): T = s.head }
val tails = new (Stream ~> Stream) { def apply[T](s: Stream[T]): Stream[T] = s.tail }

The toList function on KList has type KList[M, HL] => List[M[_]] and has a trivial implementation. Since List is homogeneous, we can’t preserve each individual cell’s type, but we can at least use the common type constructor. In ‘zipWith’, this means we can call the ‘isEmpty’ method on the elements of the list but we would not get a very specific type if we called ‘head’, for example. ‘heads’ and ‘tails’ are natural transformations that map a Stream[T] to its head of type T and its tail of type Stream[T], respectively.

The original example translated to use the generalized zipWith looks like:

val nats = Stream.from(1)
val random = Stream.continually( math.random )
val seq = zipWith( nats :^: random :^: KNil ) {
   case n :: r :: HNil => if(r > 0.3) n else -n
}

scala> seq.take(10).toList
res0: List[Int] = List(-1, 2, -3, -4, -5, 6, 7, 8, 9, 10)

We can implement the related ‘zipped’ function in terms of ‘zipWith’.

def zipped[HL <: HList](kl: KList[Stream, HL]): Stream[HL] =
   zipWith(kl)(x => x)

Or, we could have implemented zipWith in terms of zipped. In any case, we can implement several other functions using zipped:

def foreach[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Unit =
   zipped(kl).foreach(f)

def collect[HL <: HList, T](kl: KList[Stream, HL])(f: HL => Option[T]): Stream[T] =
   zipped(kl).collect(f)

def flatMap[HL <: HList, T](kl: KList[Stream, HL])(f: HL => Stream[T]): Stream[T] =
   zipped(kl).flatMap(f)

def forall[HL <: HList](kl: KList[Stream, HL])(f: HL => Boolean): Boolean =
   zippped(kl).forall(f)
      
def exists[HL <: HList](kl: KList[Stream, HL])(f: HL => Boolean): Boolean =
   zipped(kl).exists(f)

An example using ‘foreach’:

val a = Stream(1,2,5,3,9,10,101)
val b = Stream("one", "two", "three", "four")
val c = Stream(true, false, false, true, true)

zipped(a :^: b :^: c :^: KNil) foreach {
   case n :: s :: b :: HNil =>
      println( s * (if(b) 1 else n) )
}

one
twotwo
threethreethreethreethree
four
Advertisements

Type-Level Programming in Scala, Part 8b: KList basics

In the absence of rank-2 types, it can be useful to have a higher-kinded heterogeneous list, which I’ll call KList here. A KList defines a type constructor M[_] that is used to construct the type for all cells in the list. The parameter passed to this type constructor can be different for each cell, which is the heterogeneous part. One use of a KList is to define a generic zipWith function. KLists are also used in the implementation of the new task engine in sbt 0.9. Each of these applications will be described in subsequent posts.

We’ll start with the basic definition of KList, which looks like:

sealed trait KList[+M[_], HL <: HList]

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  // prepend
  def :^: [N[X] >: M[X], G](g: N[G]) = KCons(g, this)
}

sealed class KNil extends KList[Nothing, HNil] {
  def :^: [M[_], H](h: M[H]) = KCons(h, this)
}

object KNil extends KNil

object KList {
  // nicer alias for pattern matching
  val :^: = KCons
}

It looks similar to HList with the exception of the type constructor M. We keep the type of ‘head’ in KCons in two pieces: the type constructor M common to all cells in the KList and the type parameter to M that is specific to this cell. The full type of ‘head’ is then M[H].

An example construction:

  val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

This has type:

KCons[Int,java.lang.String :: HNil,List]

Note that we can mix type constructors that are compatible:

  val m = Seq(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil
  m: KCons[Int,java.lang.String :: HNil,Seq]

Ones that are not compatible crash the compiler:

val m = Seq(1, 2, 3, 4) :^: Option("str1", "str2") :^: KNil
scala.tools.nsc.symtab.Types$NoCommonType: lub/glb of incompatible types: [X]Option[X] and Seq

It is not possible to have types inferred in several cases, such as when the type constructor is Id, where type Id[X] = X :

  // does not compile
  val p = 1 :^: true :^: KNil

A key use of a KList is to apply a natural transformation to its contents. We have kept the type constructor separate from the type parameters, which means we can apply a natural transformation M ~> N to each element and preserve the underlying type parameters. As an example, consider our heterogeneous list of Lists:

  val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

and a natural transformation that takes a List and calls headOption on it:

val headOption = new (List ~> Option) {
  def apply[T](list: List[T]): Option[T] =
    list.headOption
}

Then, apply headOption to m:

val heads = m transform headOption
heads: KCons[Int,(java.lang.String :: HNil),Option] = KCons(Some(1),KCons(Some(str1),KNil))

We get a KList of Options, preserving the knowledge that the first element has type Option[Int] and the second has type Option[String].

The ‘transform’ method on KList is straightforward to implement:

sealed trait KList[+M[_], HL <: HList] {
  ...
  def transform[N[_]](f: M ~> N): KList[N, HL]
}

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  ...  
  def transform[N[_]](f: M ~> N) = KCons( f(head), tail transform f )
}

sealed class KNil extends KList[Nothing, HNil] {
  ...
  def transform[N[_]](f: Nothing ~> N) = KNil
}

We can add another method that down-converts a KList to its underlying HList. For example, we might reduce each List in our KList above to its head element:

val head = new (List ~> Id) {
  def apply[T](list: List[T]): T =
    list.head
}

val heads = m down head
heads: Int :: java.lang.String :: HNil = 1 :: str1 :: HNil

The definition of ‘down’ looks like:

sealed trait KList[+M[_], HL <: HList] {
  ...
  // For converting KList to an HList
  def down(f: M ~> Id): HL
}

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  ...
  def down(f: M ~> Id) = HCons(f(head), tail down f)
}

sealed class KNil extends KList[Nothing, HNil] {
  ...
  def down(f: Nothing ~> Id) = HNil
}

We will use ‘down’ and ‘transform’ in the next section to implement zipWith for arbitrary arity.

Type-Level Programming in Scala, Part 8a: KList motivation

In part 8, we will look at operations on arbitrary arity tuples over a type constructor. These are higher-kinded heterogeneous lists, which I’ll KLists. To motivate why we might want such a structure, we’ll start with Tuple2 for simplicity.

Consider some basic transformations on the elements of a Tuple2. If we want to apply the same function to both elements, we can require that the elements have a common supertype and that the function operates on that supertype:

def map1[A <: C,B <: C,C,D](t: (A,B), f: C => D): (D,D) =
 (f(t._1), f(t._2))

scala> map1( ("3", true), (_: Any).hashCode )
res1: (Int, Int) = (51,1231)

Or, we might want to supply two separate functions to operate on each component independently:

def map2[A,B,C,D](t: (A,B), f: A => C, g: B => D): (C,D) =
  (f(t._1), g(t._2))

scala> map2( (1, true), (_: Int) + 1, ! (_: Boolean) )
res3: (Int, Boolean) = (2,false)

Now, consider a Tuple2 where the types of both components are created by the same type constructor, such as (List[Int], List[Boolean]) or (Option[String], Option[Double]).

One useful operation on such a structure looks like:

def transform[F[_], A, B, G[_]] (k: (F[A], F[B]), g: F ~> G): (G[A], G[B]) =
  ( g(k._1), g(k._2) )

This applies the provided natural transformation to each element, preserving the underlying type parameter, but with a new type constructor. As an example, we can apply the toList transformation we defined in part 7:

val toList = new (Option ~> List) {
  def apply[T](opt: Option[T]): List[T] =
    opt.toList
}

// these are so that we get Option[T] as the type
// and not Some[T] or None
def some[T](t: T): Option[T] = Some(t)
def none[T]: Option[T] = None

scala> transform((some(3), some("str")), toList)
res5: (List[Int], List[java.lang.String]) = (List(3),List(str))

scala> transform((some(true), none[Double]), toList)
res6: (List[Boolean], List[Double]) = (List(true),List())

In part 6, we were concerned with the generalization of TupleN to arbitrary arity. In part 8, we will generalize ‘transform’ and related operations to heterogeneous lists over a type constructor.

Type-Level Programming in Scala, Part 7: Natural transformation literals

The question we are trying to answer in this post is:
How easy can we make it to construct a natural transformation?

That is, we can define an ordinary anonymous function in Scala for rank-1 types using some succinct special syntax:

   val a: Char => Boolean = _.isUpper
   val b = (_: Char).isUpper
   val c = (c: Char) => c.isUpper

We run into problems when we proceed to natural transformations. We are not able to define a function that maps an Option[T] to List[T] for every T, for example. If this is not obvious, try to define `toList` so that the following compiles:

   val toList = ...

   val a: List[Int] = toList( Some(3) )
   assert( List(3) == a )

   val b: List[Boolean] = toList( Some(true) )
   assert( List(true) == b )

In order to define a natural transformation M ~> N (here, M=Option, N=List), we have to create an anonymous class because Scala doesn’t have literals for quantified functions. So, we’ll explore in this post is how close we can get to a literal syntax.

First, one representation of a natural transformation in Scala looks like:

trait ~>[-A[_], +B[_]] {
   def apply[T](a: A[T]): B[T]
}

We use a strict argument here, but you could certainly make it call-by-name.

The filled in definition of toList in the motivating example using this representation is:

  val toList = new (Option ~> List) {
    def apply[T](opt: Option[T]): List[T] =
      opt.toList
  }

For any type T, this will turn an Option[T] into an List[T] by calling toList.

There is no simpler way to write this in plain Scala. We can’t write this as a function literal. There is no type that you can give a function literal such that you can apply `toList` to an arbitrary `Option[T]` and get back a `List[T]`. For example:

  def toList[T](opt: Option[T]): List[T] = opt.toList
  val hOptFun = toList _

The type of hOptFun is actually `Option[Nothing] => List[Nothing]` and not the quantified function `[T] Option[T] => List[T]`. Try applying hOptFun to a value:

hOptFun(Some(3))
error: type mismatch;
 found   : Int(3)
 required: Nothing
       hOptFun(Some(3))
                    ^

What can we do? Well, we can look to abstract types for some help. The idea is to define a trait representing a quantified type parameter where the quantified type is represented by an abstract type.

First, the trait:

trait Param[A[_], B[_]] {
  type T
  def in: A[T]
  def ret(out: B[T]): Unit
  def ret: B[T]
}

We will use this like so:

  val f = (p: Param[Option, List]) => p.ret( p.in.toList )

and define an implicit conversion from `Param[A, B] => Unit` to `A ~> B` :

object Param {

  implicit def pToT[A[_], B[_]](p: Param[A,B] => Unit): A~>B = new (A ~> B) {
    def apply[s](a: A[s]): B[s] = {
      val v: Param[A,B] { type T = s} = 
      
        new Param[A,B] { type T = s
          def in = a
          private var r: B[T] = _
          def ret(b: B[T]) {r = b}
          def ret: B[T] = r
        }
        
      p(v)
      v.ret
    }
  }
}

We could add logic to the original scheme to ensure `r` gets set exactly once in the mutable case, although this would be a runtime error and not a compile error. If we had dependent method and function types, we could keep it immutable:

trait Param[A[_]] {
  type T
  def in: A[T]
}
object Param {
  implicit def pToT[A[_], B[_]](f: (p: Param[A]) => B[p.T]): A~>B = new (A ~> B) {
    def apply[s](a: A[s]): B[s] = {
      val v: Param[A] { type T = s} = new Param[A] { type T = s
        def in = a
      }
      f(v)
    }
  }
}
 // usage:
val f = (p: Param[Option, List]) => p.in.toList

So, we didn’t exactly succeed. In the absence of some help from the compiler, we’re stuck with some verbosity.

In part 8, we will apply natural transformations to higher-kinded heterogeneous lists. There it will be useful to define some auxiliary types and an identity transformation :

object ~> {
   type Id[X] = X
   trait Const[A] { type Apply[B] = A }
   implicit def idEq : Id ~> Id = new (Id ~> Id) { def apply[T](a: T): T = a }
}

Related links:
http://article.gmane.org/gmane.comp.lang.scala.user/697
http://existentialtype.net/2008/05/26/revisiting-higher-rank-impredicative-polymorphism-in-scala/

Type-Level Programming in Scala, Part 6g: Type-indexed HLists

Thanks to Ross Mellgren for the impetus for adding another post to the HList part.

In 6c, we performed a variety of operations based on a position in an HList that was selected by a type-level natural number (Nat). In this post, we select the position by type. Bug #3201 makes the final syntax a bit more explicit than we’d like and bug #2741, which also affected 6c, means separate compilation crashes the compiler.

Similar to 6c, we take an HList and a type and produce an Indexed instance, which provides the value and type at a selected index and the HList before and after the index. We can reuse the implementation of Indexed by defining a few new implicits.

The original approach used a type-level function to compute the necessary Indexed type completely within the type-level:

trait HList {
   type toI[N <: Nat] <: Indexed
}

For an HList type HL and a Nat N, toI gave us the Indexed type for the position selected by the number N. We could then require an implicit Indexed parameter of type HL#toI[N] and define implicits that built up requested Indexed values.

This won’t work here, however. We want to select the position in the HList where the cell type H is the same as the requested type S. We cannot compute the Indexed type using a type-level-only solution because there is no general type-level equality function. We need to rely on implicit evidence of equality of two types using =:=. A bit more concretely, you can’t write:

   type TypeEq[A, B] <: Bool

but you can require evidence (as a value) that A and B are equal:

   def typeEq[A,B](implicit ev: A =:= B) ...

Remember from 6c that Indexed is comprised of two pieces: Indexed0, which represents the location of the pointer into the HList, and IndexedN, which represents locations before the pointer. In order to select the position by type, we will use a wrapper class that records the type S selected and the mapping from HList to Indexed:

   sealed trait Tip[S, HL <: HList, Ind <: Indexed] {
      def apply(hl: HL): Ind
   }

So, an instance of Tip for an HList HL and a type S can provide an Indexed instance on which we can call methods like ‘at’, ‘remove’, or ‘map’.

The actual work is constructing Tip instances. There is one case for Indexed0 and one for IndexedN. When we have evidence that the type of the head of an HCons cell is the same as the type we are looking for, we provide an Indexed0 value that points to this cell. Again, we wrap it in Tip in order to mark that we have selected a cell of type S and to provide a function that maps from the HCons cell to the Indexed instance that we ultimately want.

   implicit def tindexed0[S, H, T <: HList](implicit ev: S =:= H): Tip[S, H :: T, Indexed0[H, T]] =
      new Tip[S, H :: T, Indexed0[H,T]] {
         def apply(hc: H :: T) = new Indexed0[H, T](hc)
      }

Indexed0 points to the head of the selected HCons cell and references its tail. We then need to build up IndexedN instances from the terminating Indexed0 to reference the cells before the selected one. For an HCons cell of type H :: T, we require that the type S has been found in the tail T. That is, we need a Tip instance for the tail type T, searched type S, and some Indexed instance I. From this we can provide a Tip for the current cell.

   implicit def tindexedN[H, T <: HList, I <: Indexed, S](implicit iTail: Tip[S, T, I] ): Tip[S, H :: T, IndexedN[H, I]] =
      new Tip[S, H :: T, IndexedN[H, I]] {
         def apply(hc: H :: T) = new IndexedN[H, I](hc.head, iTail(hc.tail))
      }

Note that this will result in ambiguous implicits when there are multiple cells with the same type.

To connect the above to an HList for a requested type, we add a method ‘t’ to HCons:

   def t[S]: TipDummy[S, H :: T]

   sealed class TipDummy[S, HL <: HList](val hl: HL)

where H :: T is the type of the HCons cell. We then provide an implicit conversion from TipDummy to Indexed:

   implicit def tipToInd[S, HL <: HList, I <: Indexed](dummy: TipDummy[S, HL])(implicit tip: Tip[S, HL, I]): I = tip(dummy.hl)

The intermediate TipDummy accomplishes partial type parameter application. We want to be able to explicitly specify the type to select without having to provide the Indexed and HList types. We want those to be inferred. In practice, we need to explicitly call the tipToInd conversion because of Scala bug #3201. So, instead of something like:

hlist.t[Boolean].at

we have to do:

tipToInd(hlist.t[Boolean]).at

Examples (explicit calls to tipToInd are optimistically omitted):

   val x = 3 :: true :: "asfd" :: 'k' :: () :: 9.3 ::  HNil

   // get the Boolean value
      /* true */
   val b2: Boolean = x.t[Boolean].at

   // drop everything before the String 
      /* asfd :: k :: () :: 9.3 :: HNil */
   val pre = x.t[String].drop

   // replace the String value with the integer 19
      /* 3 :: true :: 19 :: k :: () :: 9.3 :: HNil */
   val rep = x.t[String].replace(19)

   // replace the Char with true if it is lowercase, false otherwise
      /* 3 :: true :: asfd :: true :: () :: 9.3 :: HNil */
   val mp = x.t[Char].map(_.isLower)

   // remove the Unit value
      /* 3 :: true :: asfd :: k :: 9.3 :: HNil */
   val rm = x.t[Unit].remove

   // remove the String and insert an HList derived from its value
      /* 3 :: true :: a :: sfd :: k :: () :: 9.3 :: HNil */
   val fmp = x.t[String].flatMap( s => s.charAt(0) :: s.substring(1) :: HNil )

   // insert a value before the Int
      /* List(3, 4) :: 3 :: true :: asfd :: k :: () :: 9.3 :: HNil */
   val ins0 = x.t[Int].insert(List(3,4))

   // insert a value before the Double
      /* 3 :: true :: asfd :: false :: k :: () :: -3.0 :: 9.3 :: HNil */
   val ins7 = x.t[Double].insert(-3.0f)

   // insert an HList before the String
      /* 3 :: true :: h :: true :: Some(3) :: None :: asfd :: k :: 9.3 :: HNil */
   val insH = rm.t[String].insertH( 'h' :: b2 :: Some(3) :: None :: HNil )

   // split the HList around the Unit value
      /* (3 :: true :: asfd :: k :: HNil, () :: -3.0 :: 9.3 :: HNil) */
   val (aa, bb) = ins7.t[Unit].splitAt

   // encoding of drop right
      /* 3 :: true :: asfd :: k :: HNil */
   val dropRight = x.reverse.t[Char].drop.reverse

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.

Type-Level Programming in Scala, Part 6e: HList Apply

We’ll continue by defining happly, a heterogeneous apply method. It takes an HList of functions and applies them to the corresponding values in an input HList, producing an HList of results.

First, the example usage looks like:

      // data HLists of type  Double :: Char :: HNil
   val y1 = 9.75 :: 'x' :: HNil
   val y2 = -2.125 :: 'X' :: HNil
   
      // The functions to apply.  z has type:
      //
      //   (Double => Double) :: (Char => Boolean) :: HNil
      //
   val z = ((_: Double) + .5) :: ( (_: Char).isUpper) :: HNil
   
      // apply to first input HList y1
   val z1 = happly(z)(y1)
   
      // check types
   val z1Types : Double :: Boolean :: HNil = z1

      // check values
   val 10.25 :: false :: HNil = z1

      // apply to second input HList y2
   val z2 = happly(z)(y2)
   
      // check types
   val z2Types : Double :: Boolean :: HNil = z2

      // check values
   val -1.625 :: true :: HNil = z2

We’ll implement happly using a type class HApply, which is essentially Function1. We can’t actually use Function1 because existing implicits related to Function1 get in the way.

sealed trait HApply[-In, +Out] {
  def apply(in: In): Out
}

The idea is that given an HList of functions, we produce an HApply that accepts an HList of parameters of the right type and produces an HList of results. For the function `z` from the example, we want an HApply of type:

HApply[ (Double :: Char :: HNil), (Double :: Boolean :: HNil)]

There are two basic cases for this: HNil and HCons. The easy case is mapping an HNil to an HNil, handled by happlyNil.

   implicit def happlyNil(h: HNil) : HApply[HNil, HNil] =
      new HApply[HNil, HNil] {
         def apply(in: HNil) = HNil
      }

As usual, HCons is the interesting case. We accept an HCons cell with a head that is a function and produce an HApply that will accept an input HCons cell of the right type. The HApply then applies the head function to the head value and recurses on the tail. The HApply to use for recursion is provided as an implicit and this is how we require that one HList is an HList entirely of functions and the other HList contains values of the right type to be provided as inputs to those functions.

   implicit def happlyCons[InH, OutH, TF <: HList, TIn <: HList, TOut <: HList]
      (implicit applyTail: TF => HApply[TIn, TOut]) =
         (h: HApply[InH :: TIn, OutH :: TOut]) =>

      new HApply[InH :: TIn, OutH :: TOut] {
         def apply(in: InH :: TIn) =
            HCons( h.head(in.head), applyTail(h.tail)(in.tail) )
      }

In the example, we have:

   val y1 = 9.75 :: 'x' :: HNil

   val z: (Double => Double) :: (Char => Boolean) :: HNil =
       ((_: Double) + .5) :: ( (_: Char).isUpper) :: HNil

So, for happly(z)(y1), our implicit is constructed with:

   happlyCons[ Double, Double, Char => Boolean :: HNil, Char :: HNil, Boolean :: HNil]( 
      happlyCons[ Char, Boolean, HNil, HNil, HNil](
         happlyNil
      )
   )

The first applyCons constructs an HApply that uses the head of z, a function of type `Double => Double`, to map an HList with a head of type Double to an HList with a head of type Double. It uses the HApply from the second happlyCons for mapping the tail of the input HList.

This second HApply uses the second element of z, a function of type `Char => Boolean`, to map an HList with a head of type Char to an HList with a head of type Boolean. Because this is the last element, the recursion ends with happlyNil mapping HNil to HNil.

Finally, we define an entry point. Given an HList of functions and an HList of arguments to those functions, we use happly to grab an HApply implicitly and produce the resulting HList with it:

   def happly[H <: HList, In <: HList, Out <: HList]
      (h: H)(in: In)(implicit toApply: H => HApply[In, Out]): Out =
         toApply(h)(in)