How to convert a free monad into a functor?

Question

The Free structure page on the Haskell wiki defines a function to convert a functor instance into a free monad:

inj :: Functor f => f a -> Free f a
inj fa = Roll $ fmap Return fa

Then, say inj [1,2,3], has type (Num t) => Free [] t. How do I define a function to return something like inj [1,2,3] back to [1,2,3]?

Answer 1

The first thing to observe is that a variation of inj makes Free into something that is almost a monad transformer.

I'll use Control.Monad.Free, from my free package on hackage, to avoid repeating everything here. This means that Roll becomes Free and Return is instead named Pure in the code below, relative to the version on the wiki.

import Control.Monad
import Control.Monad.Free -- from 'free'

instance MonadTrans Free where
    lift = Free . liftM Pure

You cannot however go in the other direction for an arbitrary Functor. However, if you have an instance of Monad on m, you can undo lifting by flattening Free m down to a single layer of the underlying monad m!

retract :: Monad f => Free f a -> f a  
retract (Pure a) = return a
retract (Free as) = as >>= retract

The name is chosen because this is a retraction of lift. So called because

retract . lift = id 

holds as shown by

retract (lift as) =                        -- by definition of lift
retract (Free (liftM Pure as)) =           -- by definition of retract
liftM Pure as >>= retract =                -- by definition of liftM
as >>= \a -> return (Pure a) >>= retract = -- first monad law
as >>= \a -> retract (Pure a)              -- by definition of retract
as >>= \a -> return a =                    -- eta reduction
as >>= return                              -- second monad law
as

so the function retract undoes the work of lift.

Since fmap = liftM, this holds for inj as well.

Note that lift . retract is not id. There simply isn't enough space to put everything in the intervening type -- the use of the monad smashes everything flat -- but lift . retract . lift . retract = lift . retract holds because lift . retract . lift . retract = lift . id . retract = lift . retract, so lift . retract is idempotent.

The problem with this 'lift' is that 'lift' is not a monad homomorphism, but is instead only a monad homomorphism 'up to retract', so this pushes the burden of preserving the monad transformer laws on the user of the lifted computations, so it makes sense to retain inj as a separate function name.

I'm actually going to go add retract to the free package right now. I needed it recently for an article I'm writing anyways.