Shapeless’ HLists and how to traverse them
In this article, I will explain the basics of
HList, polymorphic functions and
cats.Traverse and then show how to combine these concepts for the greater good. If you consider yourself familiar with shapeless and cats, feel free to skip the basics.
Type-safe data structures
One of the things I love working with Scala is the powerful type system. Though building on the rather limited, but still very effective capabilities of the JVM, Scala allows us to express very complex types which have no representation in Java or some of the other JVM languages. But why is it good to have something complex, apparently violating the good old KISS principle (Keep it simple, stupid)? The answer is easy: It saves us from having more complexity somewhere else. If a limitation of a program/function/data structure can be expressed in its type signature, the compiler will prove that this constraint is never violated. So no crashes on production and no need to write lengthy tests to prevent them. Pretty cool, right?
A simple example of a data structure allowing you to express a constraint is
cats.data.NonEmptyList[+A], basically a drop-in replacement for Scala’s built-in
scala.collection.immutable.List[+A] which doesn’t allow the list to be empty, so it is safe to access the
Yeah, that looks nice and makes sense and is totally valuable, BUT: Most of our functions don’t have constraints which are as simple as having a non-empty list, right? And creating separate data structures for every possible set of constraints doesn’t help us either, or does someone really want to create a
ThreeNormalUsersAndTwoAdminsList class? I don’t, but I still want to have a way to preserve strong compile-time guarantees. Fortunately, there are ways to achieve this. One very famous library for doing things like that in a generic way is shapeless, powering the generic & type-safe capabilities of endless popular Scala libraries in a type-safe way (circe, kittens, Monocle, Frameless and many others). It provides (among other cool things) tools to express constraints on type-level and therefore saves us from people who are not reading your API docs and handing over values your code doesn’t like (which shouldn’t anyway lead to exceptions as in the example, but that’s a different story…).
Though shapeless offers a lot, we will focus on one of the most known features of shapeless, the so-called
HList. Similar to
List from Scala’s standard library, it’s a single-linked list, constructed from an empty case (
HNil) and a “cons” case, named
::. Means we can create a new HList as easy as we’re used to:
1 :: 2 :: 3 :: HNil.
So far, so known. The interesting part is the type of our example – while standard Scala’s
List just gives us a value of type
List[Int] for this example, the
HList is typed as
Int :: Int :: Int :: shapeless.HNil. Looks more complicated, but expresses also more than the simpler
- The amount of items is encoded in the type – both the developer and the compiler know that this list has exactly three items in it – not more, not less, not anything else.
- In addition to that, the type also encodes the types of its elements (always
Intin our example).
While the first property can be seen as a generalisation of the already discussed
cats.data.NonEmptyList‘s guarantee to always contain an element, it can be achieved more easily using shapeless, see Sized. More interesting is that by encoding the types,
HList allows to store a heterogenous collection of elements. Yes, we can mix & match elements of different types and still have full type-safety – something you don’t have using
List, you’d need to do ugly things like
List[Any] combined with
.asInstanceOf…reminds me of Java 4 and is as outdated!
As we can see,
HLists are quite easy to create and access for very simple cases and everything happens in a type-safe way with list access checked at compile time – yay! Unfortunately, things get a little more difficult once we want to do more interesting things than just getting an element from a static index. Let’s look how
map works for
Ok, that is a bit more to digest than the simple
List(1, 2, 3).map(v ⇒ Some(v)) we’re used to. Let’s analyse why it is like that: As a heterogenous list, a
HList can contain a collection of values of any type. So we could have a
map method which takes a function
Any ⇒ V and then treat the result as a list containing only elements of type
V. But then we give up all type-safety and loose all the benefits of
HList – clearly not what we want. We need some kind of function which preserves the relation between the potential types of its input and the type it outputs for this input type. Of course, shapeless has us covered here, it’s called
Poly1 (there’s also
Poly2 and friends for functions with more arguments) and describes exactly such a polymorphic function. As we can see in the example, every element gets mapped to a value which has the same type, just wrapped in
Some. I won’t explain into detail how this encoding works (Miles Sabin, the maintainer of shapeless did that already), but high-level, it works like this:
- Create an
object XYZ extends Poly1. It’s important to have a stable identifier (name) here, anonymous classes lead to weird compiler errors.
- Add an implicit member for every type you want to cover using the
- If you need to have priorities between the different cases to resolve ambiguities, create a trait (by convention, many call these
XYZLowPriorityImplicits), add your members there and make your
XYZobject extend the trait. This makes the Scala compiler take them into account only if it can’t find a matching implicit in your
XYZobject. This trick can be used several times, with traits inheriting from another, if needed.
- Use this polymorphic function with any of the many methods
- In case of errors, make sure you have implicit members for all types you give as input and no conflicts between those.
Let’s see an example:
Not a very useful function, but it works as expected 🙂
Traverse a HList
As mentioned above, shapeless already offers a lot of useful stuff for working with
HList, but lately, I had a case which wasn’t covered. Luckily, it’s not hard to implement, so we’ll have a look on how to do it.
The operation is known as
traverse, for example as part of cats‘
Traverse type class. It has the following signature:
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A ⇒ G[B]): G[F[B]]
or simplified for
def traverse[G[_]: Applicative, A, B](fa: List[A])(f: A ⇒ G[B]): G[List[B]]
So, what does it do? It allows us to evaluate a function on each element of the list (or whatever we have a
Traverse instance for), but instead of just collecting the results in a
List[G[B]], it “flips”
List so that we get a
G[List[B]]. Thinking of
G as an effect, it combines all the single effects from evaluating the function on each element into a single one returning all the single results together. You might know this from Scala’s
Future.traverse which does exactly this for
Future. But thanks to cats and its type classes, we can express it in a more generic way, allowing for any effect which has an
Applicative (cats docs) instance – that includes
Future and fancy effect types like
We will look at the implementation in two steps to make it easier to understand what’s going on. First, we will look on how to implement
sequence, an operation which can be seen as simplification of
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]]
which could easily be expressed as
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] = traverse[G, A, A](identity)
So we save the “mapping” step and just flips the effects. Again, you might know
Let’s see how it looks like for
OK, I hope, I didn’t loose you here. Actually, despite looking a bit magic, it’s pretty straight-forward Scala once one is familiar with the underlying constructs:
- We define a type class for our operation called
- As for every type class, we need to define some instances to make use of it, in this case one for the empty list and for the cons case:
- Following the principle of Mathematical Induction, we describe how to handle a
HListgiven that one knows how to handle the tail (which could be the
HNilwe cover separately)
- Ergo, an instance for a seven element
HListgets constructed by seven calls to
hconsand one to
hnilcombination is very common when working with shapeless, basically all other
HListoperations have the same structure: source code.
- Following the principle of Mathematical Induction, we describe how to handle a
- For combining the two
G[_]values, we use
Applicative, but one could also enforce sequential evaluation by requiring
Monad(cats docs) and using
As we have all the necessary components ready, we just need to make use of
Cool, that works! Now we can go for our real target,
And how to use it:
Looks very much the same as
sequence, right? We just need some implicit evidence that our polymorphic function
DoubleThings) has a case for every type present inside the
HList. That was true for the first polymorphic functions
MakeSomeV2 we defined above as both had a case for any type. But in general, polymorphic functions in shapeless are not required to work for any type, but can have an arbitrary amount of cases (even none at all) for arbitrary types (even uninhabited types like
Nothing). But by requiring the implicit for the current head, our
hcons makes sure
F has a proper case – if not, it simply doesn’t compile.
Now we have working
traverse implementations for any
HList and any
Applicative. And maybe we learned something about different features of shapeless (or just refreshed them). Should be enough, right?
But in case you still feel you want more for your time spent:
- If your
G[_]is not just
Option, but some modern effect like
cats.effect.IO, you can combine it with
HListto initialise a bunch of similar resources and get the results back in a fully typed manner. We use this in one of our services in combination with folds to initialise a set of differently powerful, but very similar modules and create http4s routes for them based on their capabilities. Stay tuned, I might describe this technique in a future blog article!
- While I was writing this blog article, Oleg Pyzhcov published a very good blog article called “Traverse your HLists for fun and profit“. Sounds similar to this one? Yeah, it is – but on a different level. While I tried to write an article which can be understood by beginners and helps them getting into shapeless while providing a nice refresh for advanced shapeless users, Oleg’s article assumes you know a lot of things already. In return, he shows way more fancy tricks and deep dives into traversing
fs2.Streamas well. So once you understand the material of this article, make sure check out Oleg’s!
- I’m sure there are plenty of more ways to usefully traverse a
HList, just stay curious, keep experimenting and you’ll find some (hint: JSON parsing could be one).
- For many possible use cases, you might want to deal not only with a plain
HList, but with a record, which is a
HListwhere every element is bundled with a name. By having a name for each element, you have a generic representation of a case class, a JSON object or everything else that can be seen as a typed version of
Map[String, ?]. As an exercise, I suggest you try to extend
traverseto be able to deal with records – you can find my solution here.
Scala Developer, Basketball player and foodie.