[Haskell-cafe] Re: A question about "monad laws"

[Andrew Butterfield]

apfelmus wrote:
> Deokjae Lee wrote:
>> Tutorials about monad mention the "monad axioms" or "monad laws". The
>> tutorial "All About Monads" says that "It is up to the programmer to
>> ensure that any Monad instance he creates satisfies the monad laws".
>>
>> The following is one of the laws.
>>
>> (x >>= f) >>= g == x >>= (\v -> f v >>= g)
>>
>> However, this seems to me a kind of mathematical identity. If it is
>> mathematical identity, a programmer need not care about this law to
>> implement a monad. Can anyone give me an example implementation of
>> monad that violate this law ?
>
> I will be mean by asking the following counter question:
>
>   x + (y + z) = (x + y) + z
>
> is a mathematical identity. If it is a mathematical identity, a 
> programmer need not care about this law to implement addition + . Can 
> anyone give me an example implementation of addition that violates 
> this law?
Hugs> 1.0 + (2.5e-15 + 2.5e-15)
1.00000000000001 :: Double
Hugs> (1.0 + 2.5e-15) + 2.5e-15
1.0 :: Double

Hugs, on Pentium 4 machine  running Windows XP SP2 (all of which is 
largely irrelevant!)

This is precisely Jerzy's point - you can have many mathematical laws as 
you like but there is no guarantee
that a programming languages implementation will  satisfy them.

The above example is due to rounding errors and arises because the 
Double type in Haskell (or C, C++, whatever)
is a finite (rational) approximation to real numbers which are infinite 
(platonic) entities.

Associativity of addition applies for platonic reals, but not their 
widely used IEEE-standard approximate implementation
on standard hardware.

For monads, the situation is slightly different.
Haskell describes the signature of the monadic operators

return :: x -> m x
(>>=) :: m a -> (a -> m b) -> m b

but cannot restrict how you actually instantiate these.
It admonishes you by stating that you should obey the relevant laws, but 
cannot enforce this.

(of course, technically if you implement a dodgy monad, its not really a 
monad at all, but something
different with operators with the same name and types - also technically 
values of type Double are
not real numbers, (or true rationals either !)

let m denote the "list monad" (hypothetically). Let's instantiate:

return :: x -> [x]
return x = [x,x]

(>>=) :: [x] -> (x -> [y]) -> [y]
xs >>= f   =  concat ((map f) xs)

Let g n = [show n]

Here  (return 1 >>= g ) [1,2,3] = ["1","1","1","1","1","1"]
but  g[1,2,3] = ["1","2","3"],
thus violating the first monad law   | return 
<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:return> 
a >>= 
<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:&gt;&gt;=> 
f  =  f a

|

--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Foundations and Methods Research Group Director.
Course Director, B.A. (Mod.) in CS and ICT degrees, Year 4.
Department of Computer Science, Room F.13, O'Reilly Institute,
Trinity College, University of Dublin, Ireland.
                            http://www.cs.tcd.ie/Andrew.Butterfield/
--------------------------------------------------------------------