How to convert a free monad into a functor?

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) =开发者_Go百科> Free [] t. How do I define a function to return something like inj [1,2,3] back to [1,2,3]?

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.

As @sclv says, there's no way to directly convert from the free monad of a functor back to the functor alone in the general case. Why not?

If you recall the "free structures" page you linked to, it first talks about free monoids, before extending the same concept to talk about monads. The free monoid for a type is a list; an equivalent "convert back" function in that case would be turning a free monoid, with type [a], to a single element, with type a. This is obviously unworkable in two different ways: If the list is empty, it can't return anything; and if the list has multiple elements, it has to discard all but one.

The construction of a free monad is similar, and presents a similar problem. A free monad is defined by functor composition, which is just like regular function composition except on the type constructor. We can't write functor composition directly in Haskell, but just like f . g means \x -> f (g x), we can nest application of the type constructor. For example, composing Maybe with itself gives a type like Maybe (Maybe a).

So, in other words, where a plain functor describes a parameterized structure of some sort, the free monad of that functor describes that structure nested within itself to arbitrary depth.

So if we look at Free [] Int, it could be a single Int, a list of Ints, a list of lists of Ints, and so on.

So, just like we can only turn a free monoid (list) directly into a single item if the list is exactly one item long, we can only convert a free monad directly to the underlying functor if the nesting is exactly one layer deep.

If you're interested in general ways to take things back out of a free monad, you'll need to go a bit further--some sort of recursive fold-like operation to collapse the structure.

In the specific case of the free monad for lists, there's one obvious approach--recursively flatten the structure by stripping out the Roll and Return constructors and concatenating lists as you go. It may also be enlightening to think about why this approach works in this case, and how it relates to the structure of lists.

I don't understand why you're asking for this function, and there is in general no single function of type Free f a -> f a. However, there is an inverse to inj -- which is to say, there is a function of that type if you know that the structure is an outer Roll with one layer of Return. If there are any deeper Rolls, then this will fail with pattern match errors, so its sort of a silly thing to begin with. However, here you go:

unInj :: Functor f => Free f a -> f a
unInj (Roll x) = fmap (\(Return y) -> y) x