[Haskell-cafe] Re: Explaining monads

[Bertram Felgenhauer]

Benjamin Franksen wrote:
> Brian Brunswick wrote:
> > One thing that I keep seeing people say (not you), is that
> > monads /sequence/ side effects. This is wrong, or at
> > least a limited picture.
> > 
> > /All/ of the above structures are about combining compatible things things
> > together in a row.
> 
> I am a bit astonished.
> 
> Let's take the simplest example: Maybe. The effect in question is the
> premature abortion of a computation (when Nothing is returned). And of
> course Maybe sequences these effects, that's what you use it for: the
> _first_ action to be encountered that returns Nothing aborts the
> computation. Clearly sequencing goes on here.

"sequencing" is an overloaded term.

Dan Weston said in an earlier thread that monads sequence denotationally,
but not necessarily operationally. Brian makes the same point.
I also believe that this is an important distinction to make.

> I won't talk about List Monad because I always had difficulty understanding
> the List Monad.

Maybe that's because the distinction of denotational and operational
sequencing actually matters for the list monad.

I'll try to explain.

Consider

   a >>= b >>= c

This is equivalent to

   [()] >> a >>= b >>= c

We can think of this as defining a tree with three levels:

  - () at the root.

  - 'a' produces the children of the root.
  - 'b' and 'c' each add another level to the tree - given a node
    from the previous level, they produce the children of that node.

In other words, you *specify* a breadth first traversal of that
tree, and you *sequence* the subsequent levels of that traversal.

The catch here is lazy evaluation - each intermediate list of the
breadth first traversal is produced incrementally so what you get
at run time is actually a *depth first* traversal. As a result,
there's no nice sequencing anymore, operationally.

HTH,

Bertram

P.S.
  The explanation I gave above is deliberately simplified - it's
  actually only an explanation of the list *arrow*.

  The list monad allows the structure of the traversal to be
  different for various subtrees of a node. Consider

  [()] >> [1,2,3] >>= \n -> if odd n then [n] else [1..n] >>= \m -> [n+m]

  which produces the following tree:

    ()
    +- n=1
    |  `- 1
    +- n=2
    |  +- m=1
    |  |  `- 3
    |  `- m=2
    |     `- 4
    `- n=3
       `- 3

  This tree no longer has uniform levels. In my opinion the best way to
  think of this is operationally, as a depth first traversal.