Let’s quickly see how the (dual variant of the) Yoneda lemma can speed up some Haskell programs – more specifically ones that are repeatedly calling fmap to transform some data within a Functor.

We will be focusing on the following Functor:

A simple binary tree with data stored in the nodes, whose Functor instance lets us map a function over each a stored in our tree and whose Foldable instance lets us combine computations performed over our as.


The Coyoneda lemma, when interpreted on haskell Functors, tells us that Coyoneda f a is equivalent (isomorphic) to f a, where Coyoneda is:

We see that it holds an f b and a way to go from bs to as, effectively making it equivalent to f a if you fmap the first field on the second one. That’s also the only sensible thing we can do with such a value, as the b is hidden.

If it’s equivalent to f a, it must be a Functor too? Sure enough it is.

We see that calling fmap f amounts to “accumulating” more work in the b -> a field, possibly even changing from a given a to some other type, as allowed by fmap. This is exactly the piece of code that powers “fmap fusion”. Instead of going from f a to f b with fmap f and then to f c with fmap g, the Coyoneda representation keeps hold of the original f a, which is left untouched by the Functor instance from above, and instead simply composes f and g in that first field.

Now, we said that f a and Coyoneda f a are isomorphic but did not provide functions to prove our claim, let’s fix that right away.

Note that we do not need f to be a Functor to build a Coyoneda f a, as there’s no need to call fmap until the very end, when we have composed all our transformations and finally want to get the final result as some f a, not Coyoneda f a.

Maybe it’s still not clear to you that successive fmap calls are fused, so let’s prove it. We want to show that for two functions f :: b -> c and g :: a -> b, uncoyo . fmap f . fmap g . Coyoneda id = fmap (f . g).

Nice! And you could of course chain any number of fmap calls and they would all get fused into a single fmap call that applies the composition of all the functions you wanted to fmap.

For instance, back to our tree, let’s define some silly computations:

Now with a simple main we can compare how efficient it is to compute sumTree $ takeDepth n (transform t) by using Tree vs Coyoneda Tree as the functor on which the transformations are applied. You can find an executable module in this gist.

If we compare with and without Coyoneda for n = 23, there’s already a noticeable (and reproducible) difference:

$ time ./yo 23


$ time ./yo 23 --coyo