scodec - Part 2 - Conversions

In Part 1, we looked at the codec trait and a way to create a Codec[(A, B)] out of a Codec[A] and a Codec[B]. In this post, we’ll look at converting a Codec[A] to a Codec[B] using a type driven approach and we’ll get our feet wet with some category theory.

Consider this:

case class Point2D(x: Int, y: Int)

If we have a codec for an integer, we can create a Codec[(Int, Int)] easily using the TupleCodec from Part 1:

val int: Codec[Int] = ...
val tuple: Codec[(Int, Int)] = new TupleCodec(int, int)

Working directly with tuples isn’t pleasant, so we’d like to be able to create a Codec[Point2D] from a Codec[(Int, Int)]:

val point: Codec[Point2D] = ???

Hence, we need a function that can convert a Codec[A] to a Codec[B]. This looks like functor map, so let’s try it:

def map[A, B](ca: Codec[A])(f: A => B): Codec[B] = new Codec[B] {
  def encode(b: B): String \/ BitVector = ???
  def decode(buf: BitVector): String \/ (BitVector, B) = ???
}

Let’s start with the implementation of decode. We have:

• buf, a value of BitVector
• f, a function A => B
• ca, a Codec[A]

Using those values, we need to produce a String \/ (BitVector, B). We can use the values as jigsaw puzzle pieces and find a way to put all the proper shapes together. In this case, we can call decode on ca to get back a value of String \/ (BitVector, A). Then we can map f over the inner A to get a String \/ (BitVector, B):

def map[A, B](ca: Codec[A])(f: A => B): Codec[B] = new Codec[B] {
  def encode(b: B): String \/ BitVector = ???
  def decode(buf: BitVector): String \/ (BitVector, B) =
    ca.decode(buf) map { case (rest, a) => (rest, f(a)) }
}

So far so good. Let’s try the same type driven approach with the implementation of encode. We have:

• b, a value of B
• f, a function A => B
• ca, a Codec[A]

It seems we are at an impasse – no matter which value we start with, there’s no way to combine it with the other values. Intuitively, we know that encode should use ca.encode in its implementation, so let’s try that:

def map[A, B](ca: Codec[A])(f: A => B): Codec[B] = new Codec[B] {
  def encode(b: B): String \/ BitVector =
    ca.encode(???)
  ...
}

In order to call encode, we need a value of A but we only have a value of B. Again, relying on intuition, we know we should use b to generate a value of type A. To do so, we can just materialize a function B => A by asking for it in the signature of map:

def map[A, B](ca: Codec[A])(f: A => B, g: B => A): Codec[B] = new Codec[B] {
  def encode(b: B): String \/ BitVector =
    ca.encode(g(b))
  ...
}

Detour in to category theory

We now have a working way to convert a Codec[A] to a Codec[B] but naming the function map is awkward. We started with the name map because the problem felt like a functor map. But by the time we finished, we ended up needing two functions, f: A => B and g: B => A. Let’s rename this function to sortOfMap for now and consider a typeclass for types that support the general signature:

trait NotQuiteFunctor[F[_]] {
  def sortOfMap[A, B](fa: F[A])(f: A => B, g: B => A): F[B]
}

Searching Hoogle for this type signature doesn’t find any exact matches. Lars Hupel pointed out to me that this typeclass is actually an invariant functor or exponential functor. The sortOfMap operation is typically called invmap or xmap. Edward Kmett has a fascinating blog post exploring exponential functors (note: currently offline, see cached version). Additionally, Tony Morris’s index of functor types lists the invariant/exponential functor as well.

Now that we know the name for the typeclass we abstracted, let’s examine the laws for it. An invariant functor has two laws:

• identity - xmap(ma)(identity, identity) == ma
• composite - xmap(xmap(ma)(f1, g1))(f2, g2) == xmap(ma)(f2 compose f1, g1 compose g2)

The identity law states that xmapping with identity does not modify the input. The composite law states that function composition distributes over the xmap operation.

Note that every covariant functor (the kind of functor that us Scala developers are most familiar with) gives rise to an invariant functor that ignores the g function. Similarly, every contravariant functor (which defines def contramap[A, B](f: B => A): F[B]) gives rise to an invariant functor that ignores the f function.

Unfortunately, Scalaz 7 does not provide an InvariantFunctor typeclass. It was present in Scalaz 6 though, and as far as I can tell, it wasn’t removed deliberately. Hence, we can integrate it in to the Scalaz 7 typeclass hierarchy.

Integrating xmap

Now that we have a handle on what this operation is, we can complete the implementation in scodec:

object Codec {
  def xmap[A, B](codec: Codec[A])(f: A => B, g: B => A): Codec[B] = new Codec[B] {
    def encode(b: B): String \/ BitVector =
      codec.encode(g(b))
    def decode(buffer: BitVector): String \/ (BitVector, B) =
      codec.decode(buffer).map { case (rest, a) => (rest, f(a)) }
  }
  ...
}

We can also add xmap directly to the Codec trait to allow OO style method usage:

trait Codec[A] {
  def encode(a: A): String \/ BitVector
  def decode(b: BitVector): String \/ (BitVector, A)
  final def xmap[B](f: A => B, g: B => A): Codec[B] =
    Codec.xmap(this)(f, g)
}

Returning to our original example, we can now easily convert a Codec[(Int, Int)] in to a Codec[Point2D]:

val tuple: Codec[(Int, Int)] = new TupleCodec(int, int)
val point: Codec[Point2D] = tuple.xmap(
  { case (x, y) => Point2D(x, y) },
  { p => (p.y, p.y) }
)

Wrap Up

In this post, we used a type driven approach plus some intuition to implement the xmap operation. By abstracting out a typeclass, we learned about invariant functors.

In the next post, we’ll look at using Shapeless to simplify codec definitions and xmapping.