Understanding the use of bind in free monad

Question

I'm trying to get how free monads are working. During this I get into the monad instance of Free, which is:

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

instance (Functor f) => Monad (Free f) where
  return = Pure
  Pure a >>= k = k a
  Free m >>= k = Free ((>>= k) <$> m)

Knowing that

  -- k :: a -> Free f b
  -- m :: f (Free f a)
  -- fmap :: Functor f => (a -> b) -> f a -> f b
  -- (>>=) :: Free f a -> (a -> Free f b) -> Free f b

I can't get how this is working

Free ((>>= k) <$> m)

First of all how >>= k is even possible? k is a function and the first argument of >>= is not. It's like it bypasses the first argument and puts k as a second one leaving Free f a -> Free f b

Can anyone help me to get a better understanding of this? Thanks!

Answer 1

I don't know what this Free exactly is, however we both know that

(>>= k) <$> m == fmap (>>= k) m

so if m == f sth, then

fmap (>>= k) m == f ((>>= k) sth) == f (sth >>= k)

so everything seems to typecheck.

As suggested also in a comment, probably the only think you missed is that (.op. y) passes y as second argument to .op., unlike (.op.) y, which passes it as first argument.

Answer 2

I cannot help you with the signatures, but if I read correctly between the lines, you want to understand the signatures in order to understand what bind of a free monad of a functor is supposed to do. That I can explain, and hopefully this will also aid you in understanding the signatures you explicitly ask about.

The free monad of a functor f is a functor in the form of a tree where the values are stored in the Pure a leafs and all nodes have the shape of f. All branches have the same length, determined by the number of iterations of Free (f (Free f a)) you have done before you reach Pure a. For example, a free monad of the pair functor f = (a, a) and ten iterations of Free's will be a (perfect) binary tree of ten levels and 2^10 = 1024 a:s stored in the Pure a leafs. With f taking a type to a pair of that type, each iteration of Free (f (Free f a)) takes one "free monad of the pair functor with branches of length n"-type into a pair of two such types, making it a "free monad of the pair functor with branches of length n+1"-type.

As you know, bind takes a monad of type a and a function from a to a monad of b and produces a monad of type b. The bind of a free monad takes a tree of a:s where the branches have length n and a function from a to trees of b where the branches have length m and produces a tree of b:s where the branches have length n+m, simply by applying the function to the a in each Pure a leaf in the original tree and replacing the it with the resulting b tree. When you used to find a Pure a after you decsended n nodes, instead you will find another m levels of nodes leading to a bunch of b:s. Hence the new branch length of n + m.

As a sidenote, since you are trying to understand free monads: in category theory and adjunctions, free typically means "squeeze out information in all ways allowed from the input and store it". Bind of other monads collapses the information in their output using flat map. For example, bind of the list monad will forget the individual length information of the list of lists produced by its function from the input list. Free monads of a functor f never collapses anything, they just grow to fully accommodate all that is fed into them. The free monad of the list functor would just wrap the list of lists in another level of Free ([(Free [] a)]). This leads us to the other property associated with the term "free": there is a way to get from the free monad of a functor to any other monad of the functor. I'm not entirely sure what that means exactly in this context, though...