Applicative instance for free monad

Question

While trying to find a haskell monad that can be executed stepwise / allows threading, I discovered the free monad

data Free f a = Return a | Roll (f (Free f a))

with its monad instance

instance (Functor f) => Monad (Free f) where
  return = Return
  Return x    >>= f = f x
  Roll action >>= f = Roll $ fmap (>>= f) action

and its functor instance

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

I know that every monad is an applicative functor with pure = return and (<*>) = ap. For me, applicative functors are conceptually harder than monads. For a better understanding of applicative functors, I like to have the applicative instance without resorting to ap.

The first line for <*>is easy:

instance (Applicative f) => Applicative (Free f) where
  pure = Return
  Return f <*> x = fmap f x -- follows immediately from pure f <*> x = f <$> x
--Roll   f <*> x = Roll $ (fmap ((fmap f) <*>)) x -- wrong, does not type-check

How to define Roll f <*> x in basic terms with fmap and <*>?

Answer 1

Will this do?

instance (Functor f) => Applicative (Free f) where
  pure = Return
  Return f  <*> as  = fmap f as
  Roll faf  <*> as  = Roll (fmap (<*> as) faf)

The plan is to act only at the leaves of the tree which produces the function, so for Return, we act by applying the function to all the argument values produced by the argument action. For Roll, we just do to all the sub-actions what we intend to do to the overall action.

Crucially, what we do when we reach Return is already set before we start. We don't change our plans depending on where we are in the tree. That's the hallmark of being Applicative: the structure of the computation is fixed, so that values depend on values but actions don't.