Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Derivation of Free Monad

Tags:

haskell

monads

Control.Monad.Free implements a free monad as:

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Functor (Free f) where
  fmap f = go where
    go (Pure a)  = Pure (f a)
    go (Free fa) = Free (go <$> fa)

I am having a lot of trouble understanding the second go line, especially in the context of descriptions of what a free monad is. Can somenoe please describe how this works and why it makes Free f a a free monad?

like image 389
me2 Avatar asked Apr 13 '13 14:04

me2


People also ask

Why use free monad?

A free monad is a construction which allows you to build a monad from any Functor. Like other monads, it is a pure way to represent and manipulate computations. In particular, free monads provide a practical way to: represent stateful computations as data, and run them.

Why is a monad called a monad?

monad, (from Greek monas “unit”), an elementary individual substance that reflects the order of the world and from which material properties are derived. The term was first used by the Pythagoreans as the name of the beginning number of a series, from which all following numbers derived.

What is maybe monad?

On the type system the maybe monad is the operation X↦X∐*. The idea here is that a function X⟶Y in its Kleisli category is in the original category a function of the form X⟶Y∐* so either returns indeed a value in Y or else returns the unique element of the unit type/terminal object * – it is a partial function.


3 Answers

At this point, you're just making Free a functor rather than a monad. Of course, to be a monad, it has to be a functor as well!

I think it would be a little easier to think about if we rename the Free constructor to avoid confusion:

data Free f a = Pure a | Wrap (f (Free f a))

Now let's look at the structure of what we're building up. For the Pure case, we just have a value of type a. For the Wrap case, we have another Free f a value wrapped in the f functor.

Let's ignore the constructors for a second. That is, if we have Wrap (f (Pure a)) let's think of it as f a. This means that the structure we're building up is just f--a functor--applied repeatedly some number of times. Values of this type will look something like: f (f (f (f (f a)))). To make it more concrete, let f be [] to get: [[[[[a]]]]]. We can have as many levels of this as we want by using the Wrap constructor repeatedly; everything ends when we use Pure.

Putting the constructors back in, [[a]] would look like: Wrap [Wrap [Pure a]].

So all we're doing is taking the Pure value and repeatedly applying a functor to it.

Given this structure of a repeatedly applied functor, how would we map a function over it? For the Pure case--before we've wrapped it in f--this is pretty trivial: we just apply the function. But if we've already wrapped our value in f at least once, we have to map over the outer level and then recursively map over all the inner layers. Put another way, we have to map mapping over the Free monad over the functor f.

This is exactly what the second case of go is doing. go itself is just fmap for Free f a. <$> is fmap for f. So what we do is fmap go over f, which makes the whole thing recursive.

Since this mapping function is recursive, it can deal with an arbitrary number of levels. So we can map a function over [[a]] or [[[[a]]]] or whatever. This is why we need to fmap go when go is fmap itself--the important difference being that the first fmap works for a single layer of f and go recursively works for the whole Free f a construction.

I hope this cleared things up a bit.

like image 124
Tikhon Jelvis Avatar answered Sep 27 '22 22:09

Tikhon Jelvis


To tell you the truth, I usually just find it easier not to read the code in these simpler functions, but rather to read the types and then write the function myself. Think of it as a puzzle. You're trying to construct this:

mapFree :: Functor f => (a -> b) -> Free f a -> Free f b

So how do we do it? Well, let's take the Pure constructor first:

mapFree f (Pure a) = ...
-- I like to write comments like these while using Haskell, then usually delete 
-- them by the end:
--
-- f :: a -> b
-- a :: a

With the two type comments in there, and knowing the type of Pure, you should see the solution right away:

mapFree f (Pure a) = Pure (f a)

Now the second case:

mapFree f (Free fa) = ...
-- f  :: a -> b
-- fa :: Functor f => f (Free f a)

Well, since f is a Functor, we can actually use mapFree to apply mapFree f to the inner component of f (Free f a). So we get:

mapFree f (Free fa) = Free (fmap (mapFree f) fa)

Now, using this definition as the Functor f => Functor (Free f) instance, we get:

instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Free fa) = Free (fmap (fmap f) fa)

With a bit of work, you can verify that the definition we just arrived at here is the same thing as the one you're puzzling over. (As others have mentioned, (<$>) (defined in Control.Applicative) is just a synonym for fmap.) You may still not understand it, but you managed to write it, which for types as abstract as these is very often good enough.

As for understanding it, though, the thing that helps me is the following: think of a Free monad as a sort of list-like structure, with Pure as [] and Free as (:). From the definition of the type you should see this: Pure is the base case, and Free is the recursive case. What the fmap instance is doing is "pushing" the mapped function to the bottom of this structure, to where the Pure lives.

like image 39
Luis Casillas Avatar answered Sep 27 '22 22:09

Luis Casillas


Since I am confused myself, I answer with a question...could this be a correct substitution (relying on Tikhon's Wrap clarification)?

...
fmap g = go where
  go (Pure a)  = Pure (g a)
  go (Wrap fa) = Wrap (go <$> fa)

Substituting "fmap g" for "go", and "fmap" for "<$>" (since "<$>" is infix, 
 we flip "go" and "<$>"):

fmap g (Pure a)  = Pure (g a)
fmap g (Wrap fa) = Wrap (fmap (fmap g) fa)

Substituting "f (Free f a)" for "fa" in the last line (from the first data 
 declaration):

fmap g (Wrap fa) = Wrap ( fmap (fmap g) (f (Free f a)) )

                 = Wrap ( f ( fmap g (Free f a) ) )

                 = wrap ( f (Pure (g a) ) ) --if Free f a is Pure
                 or
                 = Wrap ( f ( fmap g (Wrap fa') ) ) --if Free f a is Wrap

The last line includes the recursion "fmap g (Wrap fa')", which would continue 
 unless Pure is encountered. 
like image 24
גלעד ברקן Avatar answered Sep 27 '22 21:09

גלעד ברקן