Hello All,
Lately I was playing with Monads again, and stumbled upon a problem that I
haven't been able to solve.
We all know that Monads satisfy some algebraic laws, in particular the
following one:
m >>= return === m
Different people can therefore have different styles of monadic
programming:
foo 0 = return 5 foo 0 = return 5
foo n = foo n =
do ... do ...
x <- foo (n-1) foo (n-1)
return x
We know that these two programs do the same.
But this is not true operationally!!
Take an arbitrary Output Monad, defined as follows (you can fill in the
details yourself):
type W a = (a, String)
instance Monad W where
m >>= k = let (a, s1) = m
(b, s2) = k a s1
in (b, s1 ++ s2)
return x = (x, "")
run :: W a -> String
run (_, s) = s
Running the two following programs for (run (foo 2000000)) resulted in two
very different space behaviors. The left one runs out of heap, where the
right one doesn't. (I tested it in hugs and hbc. Ghc2.01 created a space
leak even for the right one).
foo 0 = return 5 foo 0 = return 5
foo n = foo n =
do write "koe" do write "koe"
x <- foo (n-1) foo (n-1)
return x
My problem is: does this depend on my implementation of W? That is: are
there other implementations that have a better behavior? I understand why
there is an operational difference (there is a closure (let (b,s2) = (\x
-> return x) a in (b, s1++s2)) that needs to be evaluated), but I don't
know how to get rid of it.
Note that you don't want to be forced to write your programs in the
right-hand style. Sometimes it is necessary to do something like:
foo 0 = return 5
foo n =
do write "koe"
x <- foo (n-1)
write "aap"
return x
These kind of programs are very real; they occur a lot in the Lava
hardware description system.
Then a last remark: When encountering problems like these (turning up in
everyday programming and almost impossible to solve even for experienced
programmers), I always sigh and wish there were good solutions to this.
Space behavior is a big problem! And way more important than time
behavior, I think.
Regards,
Koen.
--
Koen Claessen,
[EMAIL PROTECTED],
http://www.cs.chalmers.se/~koen,
Chalmers University of Technology.
