override lazy val

Peregrinations of a developer in Scala land

Shapeless : not a tutorial - part 1

Until recently, shapeless have remained a mystery for me. I knew it existed for quite a long time, but it scared me so I didn’t try to use it in my projects. I kept hearing of it at my local Scala user group, even read the feature list twice, but never gave it a real shot. It even came to the point where I advised friends to use it to solve their specific problems (something along the line “I heard there is a thing named LabelledGeneric in shapeless, maybe it can help”), before I brace myself and jump into it.

The reason of my first fears where not all irrational. The documentation is rather scarce, and whereas there are many very good answers on stackoverflow (special thanks to Travis Brown) and a very welcoming gitter channel, I couldn’t find a comprehensive beginner guide that would explain the concepts used in shapeless, and what kinds of problems they can help solving.

This series of posts is not an attempt at such a tutorial but rather a recollection of the steps it took me to understand shapeless, the way I convinced myself that it is no magic, and the changes it made in my way of understanding Scala code in general. It is targeted at beginners hence experienced shapeless users may not expect learning a lot from it.

Each of the following section starts with the imports used in that section. I’ve deliberately made these imports overly verbose in an attempt to show how things are organized within shapeless, but wildcard imports are perfectly fine.

HList : the core building block

import shapeless.{HList, HNil, ::}

Heterogeneous Lists are the core abstraction of shapeless, most of its features revolve around the HList type. An heterogeneous list can have elements of arbitrary types, it will retain the types of each of its elements in its own type.

Consider the following REPL session :

scala> val myFirstHList = "foo" :: 42 :: java.util.UUID.randomUUID() :: HNil
myFirstHList: shapeless.::[String,shapeless.::[Int,shapeless.::[java.util.UUID,shapeless.HNil]]] = foo :: 42 :: 35c4acce-f018-47d7-baa0-ea2c5c9069cb :: HNil

As we can see, the inferred type for myFirstHList seems quite complex. Looking a bit harder, we find that it is in fact a kind of cons list of types, with shapeless.:: as the constructor.

Knowing that we can use infix notation for types that have exactly two parameters, we can write this type as String :: Int :: java.util.UUID :: HNil.

scala> val mySecondHList : String :: Int :: java.util.UUID :: HNil = "foo" :: 42 :: java.util.UUID.randomUUID() :: HNil
mySecondHList: shapeless.::[String,shapeless.::[Int,shapeless.::[java.util.UUID,shapeless.HNil]]] = foo :: 42 :: 49fa9131-eb09-4a14-b86e-e358b25bfbc7 :: HNil

There’s not much we can do with an arbitrary HList. We can get its head or tail if and only if it is a cons :

scala> mySecondHList.head
res2: String = foo

scala> mySecondHList.tail
res3: shapeless.::[Int,shapeless.::[java.util.UUID,shapeless.HNil]] = 42 :: 49fa9131-eb09-4a14-b86e-e358b25bfbc7 :: HNil

But if it is HNil there is no such method to call :

scala> mySecondHList.tail.tail.tail
res5: shapeless.HNil = HNil

scala> mySecondHList.tail.tail.tail.head
<console>:18: error: could not find implicit value for parameter c: shapeless.ops.hlist.IsHCons[shapeless.HNil]
       mySecondHList.tail.tail.tail.head
                                    ^

scala> mySecondHList.tail.tail.tail.tail
<console>:18: error: could not find implicit value for parameter c: shapeless.ops.hlist.IsHCons[shapeless.HNil]
       mySecondHList.tail.tail.tail.tail
                                    ^

Note that this is a compile error, and not a runtime exception like the one that arises when we try to access the head or tail of an empty List.

We can also create a new HList by prepending it a new element using shapeless.::, as we did above to instantiate myFirstHList and mySecondHList.

Finally, we can pattern match on a HList components as we would do with a standard list.

val hlist1 = 1 :: "foo" :: true :: HNil
val hlist2 = "foo" :: 2 :: true :: HNil

def thirdIsTrue(hlist: HList) = hlist match {
  case (_:Int) :: (_:String) :: true :: HNil => true
  case _ => false
}

assert(thirdIsTrue(hlist1))
assert(!thirdIsTrue(hlist2))

This is a rather scarce set of thing we can use to manipulate our hlists in an interesting way. What we would need now, is a way to express functions that work at that generic level.

Poly : a function type for the generic world

import shapeless.{ HList, HNil, ::, Poly, Poly1, Poly2, Poly3, poly}

A polymorphic function is a function that is defined for various – possibly unrelated – input types. Its output type varies according to the parameters types. The following snippet :

object MakeBigger extends Poly1 {

  // When given an Int multiply it by 100
  implicit def intCase = at[Int](_ * 100)

  // When given a String return an upper-cased version of it
  implicit def stringCase = at[String](_.toUpperCase)

}

defines a polymorphic function of one argument that is defined on Int and String and returns Int or String respectively.

It is defined as a bunch of implicit defs that mimics pattern-matching on types. The at[T] method, inherited from Poly1, takes a function as a parameter, that represent what our MakeBigger “function” does when called with an argument of type T.

The Ploy1 trait gives our MakeBigger object an apply method so we can use it as a standard function :

scala> import PolyExamples._
import PolyExamples._

scala> MakeBigger(42)
res0: Int = 4200

scala> MakeBigger("foo")
res1: String = FOO

But if we attempt to call it with an argument of an unhandled type, we get a (strange) compile error :

scala> MakeBigger(true)
<console>:14: error: could not find implicit value for parameter cse: shapeless.poly.Case[PolyExamples.MakeBigger.type,shapeless.::[Boolean,shapeless.HNil]]
       MakeBigger(true)
                 ^

Notice that we also get the same error if we widen the argument’s type up to an unhandled supertype :

scala> MakeBigger(42:Any)
<console>:14: error: could not find implicit value for parameter cse: shapeless.poly.Case[PolyExamples.MakeBigger.type,shapeless.::[Any,shapeless.HNil]]
       MakeBigger(42:Any)

So this is a completely type-safe operation, but with a poor error reporting.

Implicit resolution errors are always a bit scary. To understand these, you have no choice but to understand the inner workings of the thing you’re trying to use.

So lets take a deeper look into that MakeBigger thing. First, we can inspect the types of intCase and stringCase :

scala> :type MakeBigger.intCase
PolyExamples.MakeBigger.Case[Int]{type Result = Int}

scala> :type MakeBigger.stringCase
PolyExamples.MakeBigger.Case[String]{type Result = String}

This inner type Case[T] is inherited from Poly1; it represents the part of the definition of a Poly1 that takes care of an argument of type T. Likewise, there is a similar type Case[T, U] defined in Poly2, a Case[T,U,V] in Poly3 and so on.

All these different Case types are in fact aliases to the shapeless.poly.Case class which takes two type parameters : the type of the Poly in which this case is defined, and a hlist type that contains the case’s parameters types.

scala> MakeBigger.intCase.isInstanceOf[shapeless.poly.Case[MakeBigger.type, Int::HNil]]
res3: Boolean = true

This is exactly the kind of type scalac was unsuccessfully trying to instantiate when we called MakeBigger(true) above (but with Boolean instead of Int) !

We can now see how the apply method works for Poly1 :

  • For any Poly1 subtype F, given a argument of type T, an instance of shapeless.poly.Case[F,T::HNil] is searched in the implicit scope.
  • If we have defined a parameterless implicit method in object F that returns at[T](f) (f being a function defined on T), this method will be selected since it returns an instance of shapeless.poly.Case[F, T::HNil] and
  • The result of applying F to an argument of type T will be the one of applying f to that argument.

Not so scary after all.

Now imagine we want our MakeBigger function to operate on hlists. Say for example that we make a hlist bigger by duplicating each of its elements :

scala> MakeBigger(true :: 1.2 :: HNil)
res9: shapeless.::[Boolean,shapeless.::[Boolean,shapeless.::[Double,shapeless.::[Double,shapeless.HNil]]]] = true :: true :: 1.2 :: 1.2 :: HNil

How can we define enough Cases in MakeBigger to cover each possible HList subtype ?

The recursive definition of HList points us toward structural induction : if we can handle the empty case (HNil) and the composite case H :: T (with T a HList) then, by recursion, we can handle any possible HList.

So first we need to handle the empty case, which as usual is rather easy :


implicit def hnilCase = at[HNil](identity) // a bigger empty list is still empty

The composite case is not that much harder, but it needs to somehow call MakeBigger recursively. We would like to write something equivalent to the following :

implicit def hconsCase[H, T <: HList] = 
  at[H :: T]( l => l.head :: l.head :: MakeBigger(l.tail))

We make a hcons bigger by duplicating its head, and then making its tail bigger. But to call MakeBigger(l.tail) we need to have an implicit MakeBigger.Case[T] in scope, since l.tail is of type T.

So lets bring it into the scope by adding an implicit parameter to hconsCase for it :

implicit def hconsCase[H, T <: HList](implicit tailCase: Case[T]) = 
  at[H :: T](l => l.head :: l.head :: tailCase(l.tail))

We’re almost done, but this code won’t type check. Indeed, there is nothing in it that constrains the result of tailCase(l.tail) to be a HList we therefore cannot pass it as the left hand side of ::.

Remember what the :type command showed us earlier : the Case[X] type has an abstract type member Result, so maybe we can use that strange syntax to express our constraint on Result :

implicit def hconsCase[H, T <: HList]
(implicit tailCase: MakeBigger.Case[T]{type Result <: HList}) =
  at[H::T](l => l.head :: l.head :: MakeBigger(l.tail))

And voilà ! Our MakeBigger function is now able to operate on HLists.

The Aux trick

The syntax we used to constrain Result to be a HList in the previous example was particularly cumbersome. Fortunately, there is a nicer type alias defined inside Case :

object Case {
  type Aux[In, Out] = Case[In] { type Result = Out }
}

Using that, we could have written the previous example as :

implicit def hconsCase[H, T <: HList, BT <: HList]     
(implicit tailCase: Case.Aux[T, BT]) = 
  at[H::T](l => l.head :: l.head :: MakeBigger(l.tail))

But why bother defining Result as an abstract type member in the first place ? Couldn’t it be a regular type parameter of Case ?

In fact, regardless of the syntactic ugliness, using an abstract type member offers some convenient advantages. It allows us to refer to a Case without mentioning the result type (eg Case[String]) and, given a Case instance, we can refer to its Result type (which would not be possible if it was a regular type parameter). Using both aspects, here is how apply is defined on Poly1 :

 def apply[A](a:A)(implicit cse : poly.Case[this.type, A::HNil]): cse.Result

Notice how it is parametrized only on the input type (so that users can call it without knowing the return type), which was perfectly fine until we had to enforce some constraint over that result type (eg in the hconsCase above). And on the other hand, the Aux trick allows us to bind the abstract type member to a type variable that we constrain as we see fit. Best of two world.

To summarise these various aliasing layers, the following types are all equivalent :

MakeBigger.Case.Aux[I, O]
MakeBigger.Case[I]{ type Result = O }
shapeless.poly.Case.Aux[MakeBigger.type, I::HNil, O]
shapeless.poly.Case[MakeBigger.type, I::HNil]{ type Result = O }

Higher order Polys

We’ve seen that Poly can handle any type we want it to, provided we define a case for it. Hence we should be able to write higher order polymorphic functions that operate on polymorphic function.

Let define a polymorphic map over hlists. It will be a polymorphic function of two parameters, the first will be the polymorphic function (of one parameter) we want to map and the second, the hlist we want to map over.

object PolyMap extends Poly2 {

  implicit def hnilCase[F <: Poly1]
  : Case.Aux[F, HNil, HNil] =
    at[F, HNil]((f, l) => HNil)

  implicit def hconsCase[F <: Poly1, H, T <: HList, FT <: HList]              // free variables
  (implicit headCase: poly.Case[F, H :: HNil],                                // hypotheses
            tailMap: Case.Aux[F, T, FT])                                      //
  : Case.Aux[F, H :: T, headCase.Result :: FT] =                              // conclusion
    at[F, H :: T]((f: F, l: H :: T) => headCase(l.head) :: tailMap(f, l.tail))// proof
}

I tend to use this unusual code layout because I like to read it like so :

  • Given F a polymorphic function, H an arbitrary type, T and FT two hlist types
  • Assuming that
    • F is defined at H
    • PolyMap is defined at (F, T) and returns FT
  • We conclude that PolyMap is defined at (F, H :: T) and returns a hlist composed the result type of F at H and FT
  • Proof by construction
scala> PolyMap(MakeBigger, 42 :: "foo" :: HNil)
res1: shapeless.::[Int,shapeless.::[String,shapeless.HNil]] = 4200 :: FOO :: HNil

Writing a left fold is a little bit more involved. It requires three parameters, one for the binary polymorphic operation we want to fold with, one for the “zero” element, and one for the hlist we want to fold.

I’ve used the backtick syntax in a attempt to make the types self descriptive

object PolyFoldLeft extends Poly3 {

  implicit def hnilCase[P <: Poly, Z, L <: HNil]
  : Case.Aux[P, Z, L, Z] =
    at[P, Z, L]((p: P, z: Z, L: L) => z)

  implicit def hconsCase[F <: Poly, Z, H, T <: HList, `F(Z,H)`, `F(F(Z,H),T)`]
  (implicit op: poly.Case.Aux[F, Z :: H :: HNil, `F(Z,H)`],
            tailFold: Case.Aux[F, `F(Z,H)`, T, `F(F(Z,H),T)`])
  : Case.Aux[F, Z, H :: T, `F(F(Z,H),T)`] =
    at[F, Z, H :: T]((f: F, z: Z, l: H :: T) =>
      // beyond two parameters for a Case, we must wrap them in a HList manually
      tailFold( f :: op(z , l.head) :: l.tail :: HNil )
    )
}

Controlling the order of resolution

These recursive algorithms we use to implement our polymorphic functions are not always so simple though. Especially, clauses may not always be mutually exclusive.

Consider for example a polymorphic collect, a Poly2 that maps a Poly1 over a hlist but discards the element for which the Poly1 is not defined.

A first attempt would result in something like :

object PolyCollect { 

  implicit def hnilCase[F <: Poly, L <: HNil]
  : Case.Aux[F, L, HNil] = 
    at((f: F, l: L) => HNil)

  implicit def hconsCase0[F <: Poly, H, T <: HList, TF <: HList]
  (implicit tailCollect: Case.Aux[F, T, TF]) 
  : Case.Aux[F, H :: T, TF] =
    at[F, H::T]((f:F, l: H::T) => tailCollect(f, l.tail))

  implicit def hconsCase1[F <: Poly, H, T <: HList, HF, TF <: HList]
  (implicit headCase: poly.Case.Aux[F, H::HNil, HF],
            tailCollect: Case.Aux[F, T, TF]) 
  : Case.Aux[F, H :: T, HF :: TF] =
    at[F, H::T]((f:F, l: H::T) => headCase(l.head) :: tailCollect(f, l.tail))
}

But we have an ambiguity here : if F is defined at H, both hconsCase0 and hconsCase1 are good candidates for an implicit Case[F, H :: T] that consequently makes the implicit resolution fail.

We need to control the order of resolution so that we try the hconsCase0 if and only if the hconsCase1 is not applicable.

Fortunately, during implicit resolution, implicit members of super types are tried after all local implicit members have failed. So all we need to do is to put hconsCase0 in a super type of PolyCollect :

trait LowPriorityPolyCollect extends Poly2 {

  implicit def hconsCase0[F <: Poly, H, T <: HList, TF <: HList]
  (implicit tailCollect: Case.Aux[F, T, TF])
  : Case.Aux[F, H :: T, TF] =
    at[F, H::T]((f:F, l: H::T) => tailCollect(f, l.tail))
}

object PolyCollect extends LowPriorityPolyCollect {

  implicit def hnilCase[F <: Poly, L <: HNil]: Case.Aux[F, L, HNil] = at((f: F, l: L) => HNil)

  implicit def hconsCase1[F <: Poly, H, T <: HList, FH, FT <: HList]
  (implicit headCase: poly.Case.Aux[F, H :: HNil, FH],
            tailCollect: Case.Aux[F, T, FT])
  : Case.Aux[F, H :: T, FH :: FT] =
    at[F, H::T]((f:F, l: H :: T) => headCase(l.head) :: tailCollect(f, l.tail))
}

So we were able to implement functional operations on hlists using polymorphic functions. However, this is not how these operations (and many others in shapeless.syntax.HListOps) are actually implemented, but we will stick with our polys for now.

Conclusion

So we’re now equipped with some basic tools for generic programming. Hlists can be used to represent any product type, like tuples or case classes, and polys are useful to write type-level computations on hlists.

This remains rather abstract though. It will become more concrete in the next part were we discuss ways to convert arbitrary case classes back and forth to a generic hlist-based representation.

comments powered by Disqus

About

Hi ! I'm Valentin Kasas and this is my programming blog.

I am a happy Scala user since 2012 and here is where I recount some of my wanderings in that vast landscape.

Follow @vil1