Re: [Haskell-cafe] evaluation semantics of bind

2009/2/9 Gregg Reynolds :

On Mon, Feb 9, 2009 at 11:06 AM, Tillmann Rendel 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 http://www.eyrie.org/~zednenem/