[Haskell-cafe] Re: Explaining monads
bertram.felgenhauer at googlemail.com
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.
"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.
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.
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:
| `- 1
| +- m=1
| | `- 3
| `- m=2
| `- 4
This tree no longer has uniform levels. In my opinion the best way to
think of this is operationally, as a depth first traversal.
More information about the Haskell-Cafe