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.
Pure is easy.
The Free type contains a
Pure data constructor which lifts any
Free f a.
The trickier question is how Free gives us map, ap, and bind.
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
We can strip the first layer of Free with pattern matching.
This exposes the layer
And we can use map to lift our function over that layer.
But we still haven’t reached
We’re confronted by a second layer of
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
f until we reach the
a is exposed and we transform
For Free to give us a Monad for any Functor, two things must be accomplished.
First, we must expose
a without knowing anything about
That is why there is a layer of
Because we know how to destructure
Free, we can access
a without knowing how
Second, we must preserve the behavior of
That is why
f must have an instance of Functor.
Using map to navigate
f preserves the behavior of