How to convert a free monad to a functor?

Question

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

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

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

Answer 1

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

If you recall the “free structures” page that you linked to, they first talk about free monoids before spreading the same concept to talk about monads. A free monoid for a type is a list; the equivalent "return return" function in this case will turn a free monoid with type [a] into one element with type a . Obviously, this is not possible for two reasons: if the list is empty, it cannot return anything; and if the list contains several items, it should drop all but one.

The construction of a free monad is similar and poses a similar problem. A free monad is defined by a functor composition , which is similar to a regular composition, with the exception of the type constructor. We cannot write a functor composition directly in Haskell, but just like f . g f . g means \x -> f (gx) , we can embed a type constructor application. For example, composing Maybe with itself gives a type of type Maybe (Maybe a) .

So, in other words, if a simple functor describes a certain parameterized structure, the free monad of this functor describes this structure, nested within itself at an arbitrary depth.

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

So, like , we can turn a free monoid (list) directly into one element, if the list has exactly one element in length , we can convert the free monad directly into a base functor if the nesting is exactly one layer deep .

---

If you are interested in general ways to return things from a free monad, you need to go a little further - a kind of recursive addition operation to collapse the structure.

In the specific case of a free monad for lists, there is one obvious approach - recursively flatten the structure by separating the Roll and Return constructors and merging the lists as you go. It may also be useful to calculate why this approach works in this case and how it relates to the list structure.

Answer 2

The first thing to notice is that the inj variation makes Free something that is almost a monad transformer.

I will use Control.Monad.Free , from my free hack, to avoid repeating everything here. This means that Roll becomes Free , and Return instead called Pure in the code below, relative to the wiki version.

 import Control.Monad import Control.Monad.Free -- from 'free' instance MonadTrans Free where lift = Free . liftM Pure 

However, you cannot go in the other direction for an arbitrary Functor . However, if you have a Monad instance on m , you can cancel the lift by smoothing Free m to one layer of the underlying monad m !

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

The name is chosen because it is a retraction lift . That’s called because

 retract . lift = id 

performed as shown

 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 

therefore, the retract function cancels the lift operation.

Since fmap = liftM , this is also true for inj .

Please note that lift . retract lift . retract not id . There is simply not enough space to place everything in an intermediate type - using a monad breaks everything down to a plane, but lift . retract . lift . retract = lift . retract lift . retract . lift . retract = lift . retract lift . retract . lift . retract = lift . retract is performed because lift . retract . lift . retract = lift . id . retract = lift . retract lift . retract . lift . retract = lift . id . retract = lift . retract lift . retract . lift . retract = lift . id . retract = lift . retract , therefore lift . retract lift . retract is idempotent.

The problem with this “uplift” is that the “uplift” is not a monad homomorphism, but instead is only a “before retract” monodal monad, so this pushes the burden of preserving the laws of transformation of the monad on the user the calculations that have been taken, therefore it makes sense to save the harm as single function name.

In fact, I'm going to add retract to my free package right now. I needed this recently for an article that I am writing anyway.

Answer 3

I don’t understand why you are requesting this function, and generally there is no single function like Free fa -> fa . However, there is a converse to inj - that is, a function of this type if you know that the structure is an external Roll with a single Return layer. If there are deeper Roll s, this will lead to a failure with pattern matching errors, so for a start it will be stupid. However, here you go:

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