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.

data Free f a
  = Pure a
  | Free (f (Free f a))

instance Functor f => Applicative (Free f) where
  pure = Pure

instance Functor f => Monad (Free f) where
  return = pure

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.

instance Functor f => Functor (Free f) where
  fmap k (Pure x) = Pure (k x)

instance Functor f => Applicative (Free f) where
  (<*>) (Pure k) (Pure x) = Pure $ k x

instance Functor f => Monad (Free f) where
  (>>=) (Pure x) k = k x

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.

instance Functor f => Functor (Free f) where
  fmap k (Free x) = Free $ fmap ? x

instance Functor f => Applicative (Free f) where
  (<*>) (Pure k) (Free x) = Free $ fmap ? x
  (<*>) (Free k) x = Free $ fmap ? k

instance Functor f => Monad (Free f) where
  (>>=) (Free x) k = Free $ fmap ? x

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.

instance Functor f => Functor (Free f) where
  fmap k (Free x) = Free $ fmap (fmap k) x

instance Functor f => Applicative (Free f) where
  (<*>) (Pure k) (Free x) = Free $ fmap (fmap k) x
  (<*>) (Free k) x = Free $ fmap (<*> x) k

instance Functor f => Monad (Free f) where
  (>>=) (Free x) k = Free $ fmap (>>= k) x

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.

not' :: Functor f => Bool -> Free f Bool
not' x = return $ not x

>>= (Free (Just (Free (Just (Pure True))))) not'
Free $ fmap (>>= not') (Just (Free (Just (Pure True))))
Free $ Just $ (>>= not') (Free (Just (Pure True)))
Free $ Just $ Free $ fmap (>>= not') (Just (Pure True))
Free $ Just $ Free $ Just $ (>>= not') (Pure True)
Free $ Just $ Free $ Just $ not' True
Free $ Just $ Free $ Just $ Pure False

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.