iterM analog for FreeT

[fizruk]

For Free monad we have iterM that makes it easy to write arbitrary interpreters for the underlying functor. For FreeT we have iterT which is more like iter: we can't introduce an arbitrary monad and are forced to use the underlying one.

The problem with implementing iterM' for FreeT is that monads are not (easily) composable. But monad transformers are! This gave me the idea that iterM' should accept FreeT f (t Identity) a or (forall m. Monad m => FreeT f (t m) a as a second argument instead of FreeT f m a.

Using hoist from mmorph package iterM' can be implemented like this:

-- This is analog of 'iterM' for a 'Free' 'Monad' (@Free f = FreeT f Identity@)
iterM' :: (MFunctor t, Monad m, Functor f, Monad (t Identity), Monad (t m)) =>
  (f (t m a) -> t m a) -> FreeT f (t Identity) a -> t m a
iterM' phi = iterT phi . hoistFreeT (hoist $ return . runIdentity)

Note the similarity with iterM implementation:

-- | 'iterM' from 'Control.Monad.Trans.Free'
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
iterM phi = iterT phi . hoistFreeT (return . runIdentity)

I believe this similarity suggests I'm on the right way at least.

Without any extra dependencies (e.g. mmorph) iterM' can be alternatively defined as follows:

iterM'' :: (Monad m, Functor f, Monad (t m)) =>
  (f (t m a) -> t m a) -> (forall n. Monad n => FreeT f (t n) a) -> t m a
iterM'' phi m = iterT phi m

But that last definition forces users to write values of higher rank types.

So I suggest to add iterM' (perhaps with a better name) to the library.

[fizruk]

Apparantly, forall m. Monad m => t m a gives way more flexibility than MFunctor t => t Identity a. The reason is that ContT is not actually MFunctor (because m r in (a -> m r) -> m r is in both positive and negative positions), so one cannot turn ContT Identity a into a ContT m a, unless m is isomorphic to Identity.

[fizruk]

After thinking a bit more on this, I've managed to avoid MFunctor and foralled iterM in my code.

This is what I use now:

transform :: (Functor f, Monad m, MonadTrans t, Monad (t m))
    => (f (t m a) -> t m a) -> FreeT f m a -> t m a
transform phi = iterT phi . hoistIterT lift

runT :: (Functor f, MonadFree f m, MonadTrans t, Monad (t m))
    => FreeT f (t m) a -> t m a
runT = iterT wrapT

[fizruk]

transform is now merged in #42 as iterTM, so I close this issue.