Defining map is often straightforward. Here is map defined for the familiar functor Maybe.
An implementation of map must transform all instances of type a
to type b
.
Free is defined with two instances of the parameter a
.
The Pure
and Free
data constructors each have an instance of a
.
An implementation of map for Free must address both instances.
The implementation of map for the Pure
case resembles Maybe’s Just
case.
But defining map for the Free
case is not so straightforward.
The Free type is defined in terms of itself.
This means that we can’t access the second instance of a
so easily.
We must lift over more layers of structure:
- An outer layer
Free
- A middle layer
f
- An inner layer
Free
To see how this works, let’s specialize Free f a
to
Free Maybe Boolean
.
Map lifts the function not
over layers of Free and Maybe.
We can keep adding layers of Free
and Maybe
without changing map or the
lifted function.
No matter how many layers deep, the boolean is always transformed.
This works by calling map once for each inner layer of structure.
If map lifts a function over one layer of structure, then
fmap . fmap
lifts a function over two layers of
structure.
Thus we can preserve the structure of type f
without needing to know its type.
And we can lift over layers of arbitrary depth because the inmost map dispatches
to the implementation for Free.
Map is defined for Free recursively just as Free is defined recursively.
Sometimes typeclasses feel magical to me. But they’re not magic! They’re just data and functions. The magic feeling is a sign that I need to strengthen my mental model. Reading the implementation can be helpful. But sometimes the magic feeling lingers. Then I find it helpful to write out the evaluation of an example expression. I repeat this with more complex examples until the magic feeling fades away.
The functor instance for Free was one of those times when the magic feeling remained. So here is how our examples evaluate.