Max Hallinan

How Is Map Defined for Free?

Defining map is often straightforward. Here is map defined for the familiar functor Maybe.

fmap _ Nothing = Nothing
fmap f (Just x) = Just $ f x

An implementation of map must transform all instances of type a to type b. Free is defined with two instances of the parameter a.

data Free f a
  = Pure a
  | Free (f (Free f 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.

fmap f (Pure x) = Pure $ f x

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:

  1. An outer layer Free
  2. A middle layer f
  3. An inner layer Free

To see how this works, let’s specialize Free f a to Free Maybe Boolean.

fmap not $ Pure true
-- Pure false

fmap not $ Free (Just (Pure true))
-- Free (Just (Pure false))

Map lifts the function not over layers of Free and Maybe.

fmap not $ Free (Just (Free (Just (Pure true))))
-- Free (Just (Free (Just (Pure false))))

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.

fmap f (Free fx) = Free $ (fmap . fmap) f fx

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.

fmap not $ Pure true
Pure $ not true
Pure $ false
Pure false
fmap not $ Free (Just (Pure true))
Free $ (fmap . fmap) not (Just (Pure true))
Free $ Just $ fmap not (Pure true)
Free $ Just $ Pure $ (not true)
Free $ Just $ Pure $ false
Free $ Just (Pure false)
Free (Just (Pure false))
fmap not $ Free (Just (Free (Just (Pure true))))
Free $ (fmap . fmap) not (Just (Free (Just (Pure true))))
Free $ Just $ fmap not (Free (Just (Pure true)))
Free $ Just $ Free $ (fmap . fmap) not (Just (Pure true))
Free $ Just $ Free $ Just $ fmap not (Pure true)
Free $ Just $ Free $ Just $ Pure $ not true
Free $ Just $ Free $ Just $ Pure false
Free $ Just $ Free $ Just (Pure false)
Free $ Just $ Free (Just (Pure false))
Free $ Just (Free (Just (Pure false)))
Free (Just (Free (Just (Pure false))))