Why can't I generalize this from Monad to Applicative?

Question

I generalized hoistFree from the free package to hoistFreeM, similarly to how one can generalize fmap to Data.Traversable.mapM.

import Control.Monad
import Control.Monad.Free
import Data.Traversable as T

hoistFreeM :: (Traversable g, Monad m) =>
              (forall a. f a -> m (g a)) -> Free f b -> m (Free g b)
hoistFreeM f = go
  where go (Pure x)  = return $ Pure x
        go (Free xs) = liftM Free $ T.mapM go =<< f xs

However, I don't think there is a way to further generalize it to work with any Applicative, similarly to how one can generalize Data.Traversable.mapM to Data.Traversable.traverse. Am I correct? If so, why?

Answer 1

You can't lift an Applicative through a Free Monad because the Monad structure demands choice (via (>>=) or join) and the Applicative can't provide that. But, perhaps unsurprisingly, you can lift an Applicative through a Free Applicative

-- also from the `free` package
data Ap f a where
  Pure :: a -> Ap f a
  Ap :: f a -> Ap f (a -> b) -> Ap f b

hoistAp :: (forall a. f a -> g a) -> Ap f b -> Ap g b
hoistAp _ (Pure a) = Pure a
hoistAp f (Ap x y) = Ap (f x) (hoistAp f y)

hoistApA :: Applicative v => (forall a. f a -> v (g a)) -> Ap f b -> v (Ap g b)
hoistApA _ (Pure a) = pure (Pure a)
hoistApA f (Ap x y) = Ap <$> f x <*> hoistApA f y

-- just what you'd expect, really

---

To be more explicit, let's try generalizing hoistFreeM to hoistFreeA. It's easy enough to begin

hoistFreeA :: (Traversable f, Applicative v) =>
              (forall a. f a -> v (g a)) -> Free f b -> v (Free g b)
hoistFreeA _ (Pure a) = pure (Pure a)

And we can try to continue by analogy from hoistFreeM here. mapM becomes traverse and we can get as far as

hoistFreeA f (Free xs) = ?f $ traverse (hoistFreeA f) xs

where I've been using ?f as a makeshift type hole to try to figure out how to move forward. We can complete this definition if we can make

?f :: v (f (Free g b)) -> v (Free g b)

In other words, we need to transform that f layer into a g layer while living underneath our v layer. It's easy enough to get underneath v since v is a Functor, but the only way we have to transform f a to g a is our argument function forall a . f a -> v (g a).

We can try applying that f anyway along with a Free wrapper in order to fold up our g layer.

hoistFreeA f (Free xs) = ?f . fmap (fmap Free . f) $ traverse (hoistFreeA f) xs

But now we have to solve

?f :: v (v (Free g b)) -> v (Free g b)

which is just join, so we're stuck. This is fundamentally where we're always going to get stuck. Free Monads model Monads and thus in order to wrap over them we need to somehow join or bind.