[Haskell-cafe] evaluation semantics of bind
David Menendez
dave at zednenem.com
Mon Feb 9 23:30:01 EST 2009
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/>
More information about the Haskell-Cafe
mailing list