A simple encoding of the Freer monad

Posted on November 28, 2018

Some time ago, I came up with a pretty simple way of implementing Freer monads. After a round of googling, it looks like a variant of the van Laarhoven free monad, but still I’d like to do a brief writeup on what it is, and how it came to me :)

Recall the kind signature of Freer:

Freer takes a GADT encoding an effect, and offers >>= for free. Forget about the effect for one second:

This silly version of Freer completely ignores f, and we can’t lift f a to Freer f a. Yet it’s trivial to implement a Monad instance for Freer f, so we do get >>= for free. In this case, lifting f a to Freer f a is the same saying as “for any m which is a Monad, I demand a natural transformation from f to m”:

It’s still trivial to write a Monad instance for Freer f (just a reader monad). Since we have an extra piece of context which tells us how to convert f x to m x, it’s simple to implement lifting:

We also need a way to interpret Freer:

Just supply a natural transformation from f to the target monad. To implement a pure fold, just interpret it to Identity.

Compared to Oleg Kiselyov’s Freer implementation, this encoding is much more lightweight: it doesn’t use a type-aligned sequence to encode a chain of Kleisli arrows, so you can’t pattern match on the head or tail of that chain in O(1) time. This is similar to Edward Kmett’s Church-encoded free monads: sacrificing O(1) pattern matching to avoid quadric slowdown of left-associated >>= applications. But when you don’t really need monadic reflection, this encoding may be useful to you (a complete implementation is available here).

Additional note: we’re only handling one single effect in this post. This encoding doesn’t prevent you from implementing a coproduct of effects and a full-blown effect system; plenty of Freer libraries out there (e.g. freer-simple) already demonstrate how to do that :)