Church-encoded free monad transformer + recursion schemes

[roshanshariff]

Code here

This is a first attempt at a Church-encoded free monad transformer, represented by the type:

newtype FT f m a = FT { runFT :: forall r. (a -> m r) -> (f (m r) -> m r) -> m r }

The module includes equivalents of hoistFreeT and transFreeT from Control.Monad.Trans.Free.

There are also three recursion schemes:

cataFT :: (a -> m b) -> (f (m b) -> m b) -> FT f m a -> m b
cataFT kp kf ft = runFT ft kp kf

foldFT :: (Traversable f, Monad m) => (a -> m b) -> (f b -> m b) -> FT f m a -> m b
foldFT kp kf = cataFT kp $ kf <=< sequence

sequenceFT :: (Traversable f, Monad m, MonadFree f n) => FT f m a -> m (n a)
sequenceFT = foldFT (return . return) (return . wrap)

The code also adds analogues of these recursion schemes for the existing FreeT class. The isomorphism of FreeT and FT is witnessed by the functions toFreeT and fromFreeT.

If the cataFT and cataFreeT definitions can be moved to a type class for free monad transformers (the transformer version of MonadFree), the recursion schemes can be written generically. I'm not sure if this is a good design choice.

There are some more functions in the control-monad-free package not yet included in free. I think it would be worth porting over those that are likely to be useful.

(Note: This code is a first draft. There are only the bare minimum of type class instances, no documentation, and not very good names for the new types and functions.)

[ekmett]

Sold. Now it is just a matter of getting all the instances written.

[ekmett]

Closing this as we merged it in ~4 months ago.