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 head:

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…).

HLists

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 List[Int]:

  1. 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.
  2. In addition to that, the type also encodes the types of its elements (always Int in 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 HList:

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:

  1. Create an object XYZ extends Poly1. It’s important to have a stable identifier (name) here, anonymous classes lead to weird compiler errors.
  2. Add an implicit member for every type you want to cover using the at helper.
  3. 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 XYZ object extend the trait. This makes the Scala compiler take them into account only if it can’t find a matching implicit in your XYZ object. This trick can be used several times, with traits inheriting from another, if needed.
  4. Use this polymorphic function with any of the many methods HList comes with.
  5. 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 catsTraverse 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 List:

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” G and 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 Option, List, Future and fancy effect types like cats.effect.IO.

The implementation

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 traverse:

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 Future.sequence already.

Let’s see how it looks like for HList:

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 SequenceA
  • 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 HList given that one knows how to handle the tail (which could be the HNil we cover separately)
    • Ergo, an instance for a seven element HList gets constructed by seven calls to hcons and one to hnil
    • This hcons/hnil combination is very common when working with shapeless, basically all other HList operations have the same structure: source code.
  • For combining the two G[_] values, we use map2 from Applicative, but one could also enforce sequential evaluation by requiring Monad (cats docs) and using flatMap instead.

As we have all the necessary components ready, we just need to make use of sequence:

Cool, that works! Now we can go for our real target, traverse:

And how to use it:

Looks very much the same as sequence, right? We just need some implicit evidence that our polymorphic function F (here DoubleThings) has a case for every type present inside the HList. That was true for the first polymorphic functions MakeSome and 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.

And now?

Now we have working sequence and 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 HList to 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.Stream as 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 HList where 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 sequence and traverse to be able to deal with records – you can find my solution here.

You May Also Like

Acking (Partially) Parallelly Processed Elements

FacebookTwitterWhatsApp