A common use case when working with binary protocols is decoding a value and then using the decoded value to determine how to decode the remaining bits. For example, consider a simple framing structure, made up of a 2-byte big endian unsigned integer field followed by n bytes, where n is the value in the first field. In order to decode this structure, we need to first decode the 2-byte size field, then use the decoded size to take that number of bytes from the remainder.
This can be represented with scodec like this:
import scodec._
import scodec.bits._
import scodec.codecs._
val decoder: Decoder[ByteVector] = uint16 flatMap { size => bytes(size * 8L) }
Here, we used flatMap to express the dependency between uint16: Codec[Int] and the bytes decoder. However, flatMap on Codec returns
a Decoder[B], not a Codec[B], so by using flatMap, we lose the ability to encode.
It turns out that it is impossible to define flatMap for Codec with the expected signature. Consider this attempt:
trait Codec[A] extends Encoder[A] with Decoder[A] { self =>
def flatMap[B](f: A => Codec[B]): Codec[B] = new Codec[B] {
def sizeBound = self.sizeBound.atLeast
def decode(b: BitVector): Attempt[DecodeResult[B]] =
self.decode(b).flatMap { res => f(res.value).decode(res.remainder) }
def encode(b: B): Attempt[BitVector] =
???
}
}
The implementation of decode is straightforward, but we arrive at an impasse when trying to implement encode. We have a Codec[A], a function A => Codec[B] and a value of type B. We cannot use the Codec[A] to encode unless we have an A, and we cannot get access to a Codec[B] unless we have an A to apply to the function. Hence, we cannot implement flatMap on Codec – meaning that there is no monad for Codec!
So how were we able to call flatMap on Codec in our first example? That worked because Decoder defines a flatMap method like this:
trait Decoder[+A] { self =>
def flatMap[B](f: A => Decoder[B]): Decoder[B] = new Decoder[B] {
def decode(b: BitVector): Attempt[DecodeResult[B]] =
self.decode(b).flatMap { res => f(res.value).decode(res.remainder) }
}
}
Because Codec extends from Decoder, it inherits this definition of flatMap, which is why flat mapping a Codec results in a Decoder.
Nonetheless, we can change the signature of flatMap slightly in order to get much of the utility of flatMap without running in to our impasse when encoding. In our ill-fated attempt at implementing flatMap, we were short a value of A. Hence, we can ask the caller to provide the A value. A particularly useful way of doing so is changing the return type from Codec[B] to Codec[(A, B)].
This has implications on both decoding and encoding – when decoding, we need to return the decoded A in the overall result instead of using it solely to generate the Codec[B], whereas in encoding, we need to encode the input A, apply the function with the same A to create a Codec[B], encode the input B, and finally concatenate the encoded forms of A and B. The signature is the same as flatMap except the result type is Codec[(A, B)] instead of Codec[B] – so for now, let’s call this flatZip since it zips A and B in to a tuple.
trait Codec[A] extends Encoder[A] with Decoder[A] { self =>
def flatZip[B](f: A => Codec[B]): Codec[(A, B)] = new Codec[(A, B)] {
def sizeBound = self.sizeBound.atLeast
def decode(b: BitVector): Attempt[DecodeResult[(A, B)]] =
self.decode(b).flatMap { res =>
val a = res.value
val bres = f(a).decode(res.remainder)
bres.map { _.map { b => (a, b) } }
}
def encode(ab: (A, B)): Attempt[BitVector] = for {
encA <- self.encode(ab._1)
codecB = f(ab._1)
encB <- codecB.encode(ab._2)
} yield encA ++ encB
}
}
Another solution to the flatMap dilemma is keeping the return type as Codec[B] but adding another parameter to the method that lets us materialize an A from what we have – namely, a B.
trait Codec[A] extends Encoder[A] with Decoder[A] { self =>
def consume[B](f: A => Codec[B])(g: B => A): Codec[B] = new Codec[B] {
def sizeBound = self.sizeBound.atLeast
def decode(b: BitVector): Attempt[DecodeResult[B]] =
self.decode(b).flatMap { res => f(res.value).decode(res.remainder) }
def encode(b: B): Attempt[BitVector] = {
val a = g(b)
for {
encA <- self.encode(a)
codecB = f(a)
encB <- codecB.encode(b)
} yield encA ++ encB
}
}
}
One interesting use case for consume is handling header fields whose values are derived from the body. For instance, see this example from scodec.
An interesting property of these methods is that they can be implemented in terms of one another, as long as we have the xmap operation.
consume(f)(g) == flatZip(f).xmap[B](ab => ab._2)(b => (g(b), b))flatZip(f) == consume(a => f(a).xmap[(A, B)](b => (a, b))(ab => ab._2))(ab => ab._1)
The scodec library provides both of these methods, as they are useful in different scenarios. However, these identities show that they are just different formulations of the same concept.
A note on naming
The flatZip name leaves a lot to be desired. We selected it based on an appeal to how the method is flatMap-like in signature but returns a tuple – zipping the A and B. flatMapAndZip is way too long and a bit deceiving, as it implies that the operation is the result of composing zipping with flatMap. Additionally, we are only really zipping on the decoder side – when encoding, the user is passing the tuple to us. Zip describes the action that builds the tuple, but it would be clearer to describe the tuple itself. Using product to refer to the product type (A, B), we could call this operation flatMapProduct.
The consume name could also be improved upon. For starters, it is evocative. Worse, the rationale for its name applies equally well when using consume as an alias for flatMap. Re-examining the signature shows us that consume is like flatMap but takes an extra parameter, B => A. There doesn’t seem to be much help in naming there. Instead, let’s use our identity to help name the operation. We’ve shown that consume can be written in terms of flatMapProduct and xmap. Hence, consume is like an invariant version of the (covariant) flatMap. Informed by the fact that we use xmap as the invariant form of the (covariant) map method, we’ll call this operation xflatMap.
Knowing that flatMapProduct depends on xmap, let’s use the same convention there as well and call it xflatMapProduct.
Naming is hard.
Generalizing
Let’s extract a type class for this operation. Here, we’ll pick xflatMap as the primary operation and define xflatMapProduct in terms of xflatMap, but the inverse would be equally useful. Let’s also assume we have an invariant functor type class available:
trait InvariantFunctor[F[_]] {
def xmap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}
trait InvariantFlatMap[F[_]] extends InvariantFunctor[F] {
def xflatMap[A, B](fa: F[A])(f: A => F[B])(g: B => A): F[B]
def xflatMapProduct[A, B](fa: F[A])(f: A => F[B]): F[(A, B)] =
xflatMap[A, (A, B)](fa)(a => xmap[B, (A, B)](f(a))(b => (a, b))(ab => ab._2))(ab => ab._1)
}
What laws can we write that govern the behavior of xflatMap? We could use the same laws as the normal FlatMap type class adjusted for the extra g parameter – namely, that xflatMap is associative.
def xflatMapAssociativity[F[_], A, B, C](
fa: F[A], f: A => F[B], fi: B => A, g: B => F[C], gi: C => B
)(implicit F: InvariantFlatMap[F]): Boolean =
F.xflatMap(F.xflatMap(fa)(f)(fi))(g)(gi) ==
F.xflatMap(fa)(a => F.xflatMap(f(a))(g)(gi))(gi andThen fi)
Parallels with FlatMap
The (covariant) FlatMap type class corresponds to InvariantFlatMap in the same way that (covariant) Functor corresponds to InvariantFunctor. For example, any FlatMap instance gives rise to an InvariantFlatMap instance which simply ignores the g parameter.
What about xflatMapProduct though? There’s nothing to remove or ignore in its signature, so how can there be a correspondence to a covariant equivalent? The covariant equivalent of xflatMapProduct differs not in signature, but in implementation – specifically, it uses the covariant map instead of the invariant xmap. In fact, the covariant equivalent of xflatMapProduct is known as mproduct in Haskell – short for “monad product”, which is interesting because it does not rely on a full monad struture, but rather, only the structure of FlatMap/Bind. Naming is hard. (To be fair, mproduct exists in the Haskell standard library, which does not include the Bind type class.)
Further Generalization with Fast and Loose Reasoning
Building off these correspondences, can we create an InvariantMonad type class by adding a pure method to an InvariantFunctor?
trait InvariantMonad[F[_]] extends InvariantFlatMap[F] {
def pure[A](a: A): F[A]
}
With the associativity law inherited from InvariantFlatMap along with a left and right identity law:
def invariantMonadLeftIdentity[F[_], A, B](a: A, f: A => F[B], fi: B => A)(implicit F: InvariantMonad[F]): Boolean =
F.xflatMap(F.pure(a))(f)(fi) == f(a)
def invariantMonadRightIdentity[F[_], A](fa: F[A])(implicit F: InvariantMonad[F]): Boolean =
F.xflatMap(fa)(a => F.pure(a))(identity) == fa
We can now port arbitrary functions that work with monads to work with invariant monads – compensating for the extra inverse function as appropriate.
Parting Thoughts
Starting with a concrete example from scodec, we allowed the type system to guide us in the development of flatZip and consume. By generalizing the resulting operations, we were able to focus on the structure, with no implied meaning from binary serialization. Once we realized that we had build an invariant form of FlatMap, we were able to use loose reasoning based on correspondences with familiar type classes to develop an invariant form of Monad.
Continuously shifting between working with concrete types and working with minimally expressive type classes, allowing the findings from each style to inform the work in the opposite style, is a powerful technique in API development.
Further work will focus on development of an InvariantApplicative type class, along with finding more applications of these invariant type classes in scodec.
Acknowledgements
Special thanks to Paul Chiusano for some thoughtful discussion of these topics.