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.