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:>>=>
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/
--------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
