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?
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.
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.
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.
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With