Tue Aug 14 07:51:00 EDT 2007

```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.

but not necessarily operationally. Brian makes the same point.
I also believe that this is an important distinction to make.

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.
```