This is part 3 of a series of posts about scodec. In Part 2, we saw how to create a `Codec[A]` and xmap it in to a `Codec[B]`. In this post, we’ll show how to use Shapeless to perform automatic xmapping to case classes.

# Shapeless HLists

Shapeless is a generic programming library by Miles Sabin. One of the primary abstractions in Shapeless is the HList, or heterogeneous list. An HList represents a list of values of arbitrary types where the type of each element is preserved during compilation. For example:

``````val foo = 1 :: true :: "yes" :: Nil
val bar = 1 :: true :: "yes" :: HNil
``````

The type of `foo` is `List[Any]` because `Any` is the least upper bound of `Int`, `Boolean`, and `String`. The type of `bar` is `Int :: Boolean :: String :: HNil`. The number of list elements and the type of each element is preserved.

For a fantastic introduction to HLists, see Miles’s recent talk at flatMap(Oslo).

Shapeless supports converting an HList of the proper type to a case class instance and vice-versa. For example:

``````case class Point3D(x: Int, y: Int, z: Int)

val pointIso: Iso[Point3D, Int :: Int :: Int :: HNil] =
Iso.hlist(Point3D.apply _, Point3D.unapply _)

val components = 1 :: 2 :: 3 :: HNil
val point = pointIso.from(components) // Point(1, 2, 3)
val backToComponents = pointIso.to(point) // 1 :: 2 :: 3 :: HNil
``````

The key abstraction here is `Iso`, which represents an isomorphism between two types. `Iso` is defined in Shapeless source like this:

``````trait Iso[T, U] { self =>
def to(t : T) : U
def from(u : U) : T
...
}
``````

The `Iso` companion object defines the `hlist` method, which returns an isomorphism between a case class and an HList of the appropriate shape given the case class’s `apply` and `unapply` methods. Typically, the iso is defined as an implicit val in the companion object of the case class to allow other modules implicit access to it. Additionally, it’s type is typically inferred. So we’d actually write this:

``````case class Point3D(x: Int, y: Int, z: Int)

object Point3D {
implicit val hlistIso = Iso.hlist(Point3D.apply _, Point3D.unapply _)
}
``````

(Note: the macro-paradise branch of Shapeless removes the need for this boilerplate. Instead, an equivalent isomorphism can be summoned when needed via `Iso[Point3D, Int :: Int :: Int :: HNil]`. The macro-paradise branch uses new macro features from Eugene Burmako’s branch of Scala. For more information, see Miles’s talk at NEScala 2013. For a discussion on new macro features, see scala-internals.)

# HList Codecs

Given a codec for an HList and an iso between the HList type and a case class, we can use `xmap` to convert the codec:

``````val comps: Codec[Int :: Int :: Int :: HNil] = ???
val points: Codec[Points3D] = comps.xmap(Point3D.hlistIso.from, Point3D.hlistIso.to)
``````

This is an extremely common operation, so we let’s add direct support for it. We can add a method to `Codec` that takes an `Iso` and delegates to `xmap`. Further, we can make the iso parameter implicit, allowing the compiler to find the right iso automatically:

``````trait Codec[A] {
def encode(a: A): Error \/ BitVector
def decode(bits: BitVector): Error \/ (BitVector, A)
...
final def as[B](implicit iso: Iso[B, A]): Codec[B] = Codec.xmap(this)(iso.from, iso.to)
}
``````

This allows our point example to be rewritten as:

``````val comps: Codec[Int :: Int :: Int :: HNil] = ???
val points: Codec[Points3D] = comps.as[Points3D]
``````

# Constructing HList Codecs

So once we have a codec for an HList, we can easily convert it to a codec for a case class, but how can we create an HList codec? There’s always the option to extend `Codec` directly but we’d prefer something more compositional in nature – some way to create the codec from smaller codecs.

## HList of Codecs

One way of accomplishing this is to create an HList of codecs:

``````val int: Codec[Int] = ...
val threeInts = int :: int :: int :: HNil
``````

The type of `threeInts` is `Codec[Int] :: Codec[Int] :: Codec[Int] :: HNil` but we want a `Codec[Int :: Int :: Int :: HNil]`. It looks like an applicative sequence operation on the HList would do the trick but there’s no `Applicative` instance for `Codec` (remember in part 2, we showed that `Codec` does not have a covariant functor instance, therefore, there cannot be an `Applicative` instance). Instead, we can implement this conversion directly by folding right over the elements of the HList. Our starting value is simply a `Codec[HNil]` and the fold operation prepends a specific codec on to the accumulated HList codec.

Let’s start by implementing the empty case and the fold operation:

``````object HListCodec {

val hnilCodec: Codec[HNil] = new Codec[HNil] {
def encode(hn: HNil) = \/-(BitVector.empty)
def decode(buffer: BitVector) = \/-((buffer, HNil))
}

def prepend[A, L <: HList](a: Codec[A], l: Codec[L]): Codec[A :: L] =
new Codec[A :: L] {
override def encode(xs: A :: L) = Codec.encodeBoth(a, l)(xs.head, xs.tail)
override def decode(buffer: BitVector) = (for {
decA <- Codec.DecodingContext(a.decode)
decL <- Codec.DecodingContext(l.decode)
} yield decA :: decL).run(buffer)
}
}
``````

The `prepend` method’s type signature is interesting. Every specific HList (e.g., `Int :: Int :: Int :: HNil`) is a subtype of the HList type. The signature of `prepend` takes advantage of that in order to take a `Codec[L]` where `L` is any HList type. Further, it uses `L` in its return type, along with the cons (`::`) type operator, to declare that a `Codec[A :: L]` is returned. As a result, `encode` can split its argument in to an `A` and an `L` via `head` and `tail` respectively, and use the `encodeBoth` function we implemented in part 1. Similarly, `decode` can decode an `A` and an `L` and then put them together with the cons value operator.

Now let’s use these with `foldRight`:

``````object HListCodec {
...
def apply[L <: HList](l: L) =
l.foldRight(hnilCodec)(prepend)
}
``````

There are two issues with this implementation though. The first is that `foldRight` on HList takes a `Poly2` as its second argument, not a regular monomorhpic function. Second, our type signature claims to work with all HLists, regardless of their contents, but we only want to accept `HLists` where each element is a `Codec` of an arbitrary type.

Let’s lift `prepend` in to a `Poly2` instance:

``````object HListCodec {
...
object Prepend extends Poly2 {
implicit def caseCodecAndCodecHList[A, L <: HList] =
at[Codec[A], Codec[L]](prepend)
}
}
``````

Now we need to limit the type of `HLists` that can be passed to apply. We can do this by asking (the compiler) for evidence that each member of `L` is a `Codec` of an arbitrary type. Shapeless supports this via `UnaryTCConstraint`:

``````object HListCodec {
...
import UnaryTCConstraint._
def apply[L <: HList : *->*[Codec]#λ](l: L) =
l.foldRight(hnilCodec)(Prepend)
}
``````

Compiling this shows that we aren’t quite done: `could not find implicit value for parameter folder: shapeless.RightFolder[L,scodec.Codec[shapeless.HNil],scodec.HListCodec.Prepend.type]`

This is due to the `foldRight` operation requiring an implicit `RightFolder` parameter. In general, when can solve these types of errors by adding implicit parameters to our function signature. In this case, by requiring an implicit `RightFolder` of the specified type:

``````object HListCodec {
...
import UnaryTCConstraint._
def apply[L <: HList : *->*[Codec]#λ](l: L)(
implicit folder: RightFolder[L, Codec[HNil], Prepend.type]
) = l.foldRight(hnilCodec)(Prepend)
}
``````

We can stop at this point if we want - the implementation is now fully functional. If we want to be explicit about the return type of `apply`, we have one more step. Namely, we need to indicate that `apply` returns a `Codec[M]` where `M` is an HList. Further, we need to describe the relationship between `L` and `M`, which is provided by `RightFolderAux` - an alternative to `RightFolder` that lets us use the result type:

``````object HListCodec {
...
import UnaryTCConstraint._
def apply[L <: HList : *->*[Codec]#λ, M <: HList](l: L)(
implicit folder: RightFolderAux[L, Codec[HNil], Prepend.type, Codec[M]]
): Codec[M] = l.foldRight(hnilCodec)(Prepend)
}
``````

## Prepending a codec on to an HList codec

Now that we have a way to construct HList codecs, let’s consider other operations on them. For starters, consider combining a `Codec[A]` with a `Codec[L]` where `L` is an HList. We built this combinator earlier – the `prepend` method used in the call to `foldRight` when constructing an HList codec. We can add an operator to HList codecs that aliases `prepend`:

``````implicit class EnrichedHListCodec[L <: HList](l: Codec[L]) {
def ::[A](a: Codec[A]): Codec[A :: L] = HListCodec.prepend(a, l)
}
``````

Now we can cons codecs on the the front of an HList codec with `::`. For example:

``````val comps = int :: int :: int :: HListCodec.hnilCodec
``````

We can further simplify this by defining the `::` operator on a non-HList codec as well. Calling `::` on a non-HList codec should prepend the left codec on to the result of the right codec prepended to `Codec[HNil]`:

``````implicit class EnrichedCodec[A](codecA: Codec[A]) {
def ::[B](codecB: Codec[B]): Codec[B :: A :: HNil] =
HListCodec.prepend(codecB, HListCodec.prepend(codecA, HListCodec.hnilCodec))
}
``````

This lets us write the `Points3D` codec as:

``````val points = (int :: int :: int).as[Points3D]
``````

## Appending a codec on to an HList codec

Similarly, we can imagine the need to append a `Codec[A]` on to the end of a `Codec[L]`. We don’t have a convenient type operator to represent the result of appending `A` to `L` so we’ll just define a new type parameter `LA` and require implicit evidence that ensures `LA` represents the list with `A` appended to the end of `L`.

``````object HListCodec {
def append[L <: HList, A, LA <: HList](
l: Codec[L], a: Codec[A]
)(implicit ???
): Codec[LA] = new Codec[LA] {
override def encode(xs: LA) = ???
override def decode(buffer: BitVector) = ???
}
}
``````

Let’s start with the implementation of decode. We can decode with `l` and then with `a` and then append the result from `a` on to the end of the result from `l`. For the implementation of encode, we need to take everything but the last element out of the provided value of type `LA` and encode it with `l`. Then we need to take the last element from the value of type `LA` and encode it with `a`:

``````object HListCodec {
def append[L <: HList, A, LA <: HList](
l: Codec[L], a: Codec[A]
)(implicit ???
): Codec[LA] = new Codec[LA] {
override def encode(xs: LA) = Codec.encodeBoth(l, a)(xs.init, xs.last)
override def decode(buffer: BitVector) = (for {
decL <- Codec.DecodingContext(l.decode)
decA <- Codec.DecodingContext(a.decode)
} yield decL :+ decA).run(buffer)
}
}
``````

Compiling this and inspecting the implicits that Shapeless needs causes us to add an implicit for the call to `init`, and implicit for the call to `last`, and an implicit for the call to `:+`. For the implicits supporting `init` and `last`, we need to further refine the return type of each by specifying the output type:

``````object HListCodec {
def append[L <: HList, A, LA <: HList](l: Codec[L], a: Codec[A])(implicit
prepend: PrependAux[L, A :: HNil, LA],
init: Init[LA] { type Out = L },
last: Last[LA] { type Out = A }
): Codec[LA] = new Codec[LA] {
override def encode(xs: LA) = Codec.encodeBoth(l, a)(xs.init, xs.last)
override def decode(buffer: BitVector) = (for {
decL <- Codec.DecodingContext(l.decode)
decA <- Codec.DecodingContext(a.decode)
} yield decL :+ decA).run(buffer)
}
}
``````

And we can provide syntax support for this as well:

``````implicit class EnrichedHListCodec[L <: HList](l: Codec[L]) {
...
def :+[A, LA <: HList](a: Codec[A])(implicit
prepend: PrependAux[L, A :: HNil, LA],
init: Init[LA] { type Out = L },
last: Last[LA] { type Out = A }
): Codec[LA] = append(l, a)
}
``````

## Concatenating HList codecs

Finally, we can concatenate two HList codecs. We can concatenate a `Codec[K]` with a `Codec[L]` in to a `Codec[KL]`. In the same way we did with the `append` method, we’ll just invent the type parameter `KL` and then require evidence that it has the structure of `K` concatenated with `L`:

``````def concat[K <: HList, L <: HList, KL <: HList](ck: Codec[K], cl: Codec[L])(
implicit ???
): Codec[KL] = new Codec[KL] {
override def encode(xs: KL) = ???
override def decode(buffer: BitVector) = ???
}
``````

As usual, we’ll start with the implementation of decode. We can use the same basic template as we used in `append` but instead of appending a single element, we’ll just concatenate the result of each decode operation. The compiler informs us that we need a `Prepend` implicit in scope. This time, we want to bind the result of concatenation to the `KL` type parameter so we’ll use `PrependAux` instead:

``````def concat[K <: HList, L <: HList, KL <: HList, KLen <: Nat](ck: Codec[K], cl: Codec[L])(implicit
prepend: PrependAux[K, L, KL]
): Codec[KL] = new Codec[KL] {
override def encode(xs: KL) = ???
override def decode(buffer: BitVector) = (for {
decK <- Codec.DecodingContext(ck.decode)
decL <- Codec.DecodingContext(cl.decode)
} yield decK ::: decL).run(buffer)
}
``````

To encode, we need to split the provided HList of type `KL` in to two HLists – one of `K` and one of `L`. A feature of HLists is that they encode their length in to their static type. Hence, we can get the length of `K` and split the provided `KL` at that position, yielding two HLists – one of type `K` and another of type `L`. Because we are splitting `KL` with a statically known length, the `split` method needs a type encoding of the length. Hence, we need to add another type parameter to the method that represents the length of list `K` - called ‘KLen’. We then need to bind the length of `K` to that parameter. Finally, we need an implicit `Split` parameter for splitting `KL` at position `KLen`:

``````def concat[K <: HList, L <: HList, KL <: HList, KLen <: Nat](
ck: Codec[K], cl: Codec[L]
)(implicit
prepend: PrependAux[K, L, KL],
lengthK: Length[K] { type Out = KLen },
split: Split[KL, KLen] { type P = K; type S = L }
): Codec[KL] = new Codec[KL] {
override def encode(xs: KL) = {
val (k, l) = xs.split[KLen]
Codec.encodeBoth(ck, cl)(k, l)
}
override def decode(buffer: BitVector) = (for {
decK <- Codec.DecodingContext(ck.decode)
decL <- Codec.DecodingContext(cl.decode)
} yield decK ::: decL).run(buffer)
}
``````

Syntax support follow the same pattern as before:

``````implicit class EnrichedHListCodec[L <: HList](l: Codec[L]) {
def :::[K <: HList, KL <: HList, KLen <: Nat](k: Codec[K])(implicit
prepend: PrependAux[K, L, KL],
lengthK: Length[K] { type Out = KLen },
split: Split[KL, KLen] { type P = K; type S = L }
): Codec[KL] = concat(k, l)
}
``````

# Wrap Up

In this post we looked at how scodec uses Shapeless to provide type-safe binding of binary structures to case classes. In the process, we’ve explored some type-level generic programming.