Free gives us a Monad instance for any Functor.
If map is defined for `f a`

, then bind is defined for `Free f a`

.
And just like any Monad, we have an Applicative instance too.
We get these instances for free, without implementing the operations by hand.
But how?

Pure is easy.
The Free type contains a `Pure`

data constructor which lifts any `a`

into
`Free f a`

.

The trickier question is how Free gives us map, ap, and bind.

Again, the `Pure`

case is straightforward.
We can destructure `Pure`

and apply our function to `a`

just as we would for
common Functors like Maybe and Either.

It’s the Free case that trips us up.
How do we reach `a`

when it’s encased in layers of `Free`

and `f`

?
We can strip the first layer of Free with pattern matching.
This exposes the layer `f`

.
And we can use map to lift our function over that layer.
But we still haven’t reached `a`

.
We’re confronted by a second layer of `Free`

.

Free is a recursive type.
So the definitions of map, ap, and bind must also be recursive.
Instead of lifting the function `k`

over the structure `f`

, we lift a recursive
call to map, ap, or bind.

`Pure`

is the base case of that recursion.
We keep expanding the recursive chain of `Free`

and `f`

until we reach the
`Pure`

case.
Then `a`

is exposed and we transform `a`

into `b`

.

For Free to give us a Monad for any Functor, two things must be accomplished.
First, we must expose `a`

without knowing anything about `f`

.
That is why there is a layer of `Free`

between `f`

and `a`

.
Because we know how to destructure `Free`

, we can access `a`

without knowing how
to destructure `f`

.
Second, we must preserve the behavior of `f`

.
That is why `f`

must have an instance of Functor.
Using map to navigate `f`

preserves the behavior of `f`

.