# 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 def`

s 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 `Case`

s 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 `HList`

s.

## 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.