Implementing `MyMonad Free f`

Question

Typeclassopedia defines the Free monad data type.

data Free f a = Var a | Node (f (Free f a))

Given:

class (MyMonad m) where
    ret     :: a         -> m a
    flatMap :: m a -> (a -> m b) -> m b

Here's my incomplete attempt at implementing the MyMonad instance of this typeclass.

instance Functor f => MyMonad (Free f) where
  ret                 = Var
  flatMap (Var x)  f  = f x 
  flatMap (Node xs) f = error

Please help me reason about what >>=/binding means over a Free monad.

When I struggled with implementing Applicative (Free f), I was encouraged to try to implement the Monad instance.

Answer 1

In these kinds of situations, typed holes can help with how to proceed. They give information about the type the still unimplemented "hole" should have.

Using a typed hole instead of error in your definition:

instance Functor f => MyMonad (Free f) where
    ret                 = Var
    flatMap (Var x)  g  = f x
    flatMap (Node xs) g = _

Gives an error message like (here simplified):

Found hole `_' with type: Free f b
...
Relevant bindings include
  g :: a -> Free f b (bound at Main.hs:10:21)
  xs :: f (Free f a) (bound at Main.hs:10:17)
  flatMap :: Free f a -> (a -> Free f b) -> Free f b
    (bound at Main.hs:9:3)

That Free f b in the hole... which constructor should it have? Var or Node?

Now, a value of type Free a is like a tree that has values of type a on the leaves (the Var constructor) and whose branching nodes are "shaped" by the functor f.

What is >>= for Free? Think of it as taking a tree and "grafting" new trees on each of its leaves. These new trees are constructed from the values in the leaves using the function that is passed to >>=.

This helps us continue: now we know that the constructor on the right of the flatMap (Node xs) f = _ pattern must be Node, because "grafting" new things onto the tree never collapses already existing nodes into leaves, it only expands leaves into whole new trees.

Still using type holes:

instance Functor f => MyMonad (Free f) where
    ret                 = Var
    flatMap (Var x)  g  = f x
    flatMap (Node xs) g = Node _

Found hole `_' with type: f (Free f b)
...
Relevant bindings include
g :: a -> Free f b (bound at Main.hs:10:21)
xs :: f (Free f a) (bound at Main.hs:10:17)

In xs we have a Free f a wrapped in a f, but f is a functor and we could easily map over it.

But how to convert that Free f a into the Free f b required by the hole? Intuitively, this Free f a will be "smaller" that the one the >>= started with, because we have stripped one "branching node". Maybe it is even a leaf node, like the case covered by the other pattern-match! This suggests using recursion of some kind.

Answer 2

Start by implementing the Functor instance. Then note that in general, a monad can be described as a functor that supports return and join :: m (m a) -> m a. Can you see how to implement join using =<< and return? Can you see how to implement =<< using fmap and join?

Spoilers

As you indicated,

data Free f a = Var a | Node (f (Free f a))

So (as you could work out with typed holes)

join :: Functor f => Free f (Free f a) -> Free f a
join (Var a) = a
join (Node m) = Node (fmap join m)

It might be useful to think about the geometry here. We descend the tree recursively, leaving the structure the same, until we get to the leaves, which we unwrap.

Note: =<< is the flipped version of >>=; it's more consistent with the other composition operators. $, <$>, <*>, ., =<<, and <=< all match up so you can read an expression using them from left to right or right to left without having to switch directions a few times in the middle.