[Haskell-cafe] evaluation semantics of bind

[David Menendez]

2009/2/9 Gregg Reynolds <dev at mobileink.com>:
> On Mon, Feb 9, 2009 at 11:06 AM, Tillmann Rendel <rendel at cs.au.dk> wrote:
>>
>> Gregg Reynolds wrote::
>>>
>>> My original question was motivated by the observation that a human reader
>>> of
>>> an expression of the form "e >>= f" , on seeing that f is constant, may
>>> pull
>>> the constant value out of f, disregard e and dispense with the
>>> application f
>>> e.
>>
>> While a human reader may well do that, but it would be correct or wrong
>> depending on the definition of >>=. The same is of course true for
>> compilers. By the way, there is no "application f e".
>
> I guess it would help if I got the notation right.  My intended meaning was
> f* e, where * is the Kleisli star.  Sorry about that.

You can't assume f* is a constant function just because f is. In fact,
in most monads (excluding Identity and Reader) f* is never constant.

>> 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.  :(

Here are two ways to think about it.

First, you can decompose the Kleisli star into two operations. That
is, for a monad T with multiplication mu,

   f* = mu . T f

Or in Haskell notation,

    (f =<<) = join . fmap f

For the list monad, join is concat and fmap is map. So we have,

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

Second, in the list monad, we have a distributive law relating mplus and >>=.

    mplus x y >>= f = mplus (x >>= f) (y >>= f)

We can rewrite [1,2] >>= \x -> [21] as

    mplus (return 1) (return 2) >>= \x -> return 21

then we can distribute >>=,

    mplus (return 1 >>= \x -> return 21) (return 2 >>= \x -> return 21)

then by the monad laws,

    mplus (return 21) (return 21)

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>