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
Free is defined with two instances of the parameter
Free data constructors each have an instance of
An implementation of map for Free must address both instances.
The implementation of map for the
Pure case resembles Maybe’s
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
- A middle layer
- An inner layer
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
Maybe without changing map or the
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
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.