wren ng thornton wren at freegeek.org
Mon Feb 9 23:52:31 EST 2009

```Gregg Reynolds wrote:
> Tillmann Rendel wrote:
> > An example where it would be wrong to ignore e:
> >
> >  sum ([1, 2] >>= const [21])
> >
> > This expression should evaluate to sum [21, 21] = 42, not sum [21] = 21.
> >
>
> Sigh.  I hate it when this happens.  Just when I thought I had it figured
> out, it turns out I'm clueless.  This is very enlightening and should
> definitely be included in any monad tutorial.  Actually you don't even need
> "sum" and "const" to demo the point,  "[1,2] >>= \x -> [21]" evals to "[21,
> 21]" in ghci.  And I have absolutely no idea why.  Very mysterious, the
> Kleisli star.  :(

Just walk through the evaluation step by step, it's not so mysterious.

[1,2] >>= \x -> [21]
== {CT definition of bind}
join . fmap (\x -> [21]) \$ [1,2]
==
join [(\x -> [21]) 1, (\x -> [21]) 2]
==
join [[21],[21]]
==
[21,21]

Or if you prefer to use the Haskell function definitions instead of the
category theory definitions (it's all the same):

[1,2] >>= \x -> [21]
==
concatMap (\x -> [21]) [1,2]
==
concat . map (\x -> [21]) \$ [1,2]
==
concat [(\x -> [21]) 1, (\x -> [21]) 2]
==
concat [[21],[21]]
==
[21,21]

This is exactly the point I was raising earlier. The "statefullness" of
monads has nothing to do with IO, but every monad has some of it. In
general it is wrong to throw it away just because the function passed to
bind happens to ignore the value associated with it. There are some
cases where that can be correct, but in general it is not.

For lists, we can envision the statefullness as a path through a
decision tree. To get the intuition right, it's easiest to pretend that
we never call join (or that join does nothing). If we don't call join,
eventually after a number of binds or maps we'll end up with some value
of type [[...[a]...]]. We can draw that value out as a B-tree where each
level has a branch of whatever arity it needs. In this B-tree, every
leaf is associated with a unique path through the tree and therefore
they can be distinguished.

The reason the above example works the way it does is that the initial
list has two leaves each associated with their unique paths through this
tree of choices. The function passed into bind is a continuation of
sorts. So, given that we can non-deterministically choose either of the
paths in the original tree, for each choice we must then continue with
(\x -> [21]) applied to the seed value for that choice (1 or 2, as
appropriate). Because we had two choices initially, and from there we
have only one choice, we will have 2*1 choices in the end:

/\
/  \
(1) (2)
|   |
|   |
21   21

If we imagine a finite state automaton, we might think that the two 21s
could be collapsed together since they represent the same "state". But
that is not so: the list monad is for *paths* through an FSA not for
states in an FSA. (For states in an FSA we'd want the set monad
instead.) Of course for the list monad we don't actually keep around the
decision tree. In fact lists generalize over all possible decision trees
which could yield the given distribution of path-endpoints, so it's not
quite the way envisioned above.

--
Live well,
~wren
```