[Haskell-cafe] evaluation semantics of bind

[wren ng thornton]

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