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/ --------------------------------------------------------------------