[Haskellcafe] Re: A question about "monad laws"
Andrew Butterfield
Andrew.Butterfield at cs.tcd.ie
Mon Feb 11 10:35:23 EST 2008
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.5e15 + 2.5e15)
1.00000000000001 :: Double
Hugs> (1.0 + 2.5e15) + 2.5e15
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 IEEEstandard 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:>>=>
f = f a


Andrew Butterfield Tel: +35318962517 Fax: +35316772204
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/

More information about the HaskellCafe
mailing list