Hello, I hope I understand what's going on; if not please someone correct me.
I have problems with monads and memory. I have a monad through which I thread output. If I do the concatenation of the output-strings in one way Hugs runs out of memory, but if I do it in another way everything works. I can't see why the first way doesn't work but the second is OK. I woudl appreciate if someone could tell me what I am doing wrong. Here is the non-working monad: -}
The problem is not directly connected to monads; what is the problem: [] ++ x = x (h:t) ++ x = h : (t++x), i.e. time complexity of ++ is proportional to the length of first list. first way:
putCharM c = M $ \o -> ((), o ++ [c]) -- Is this stupid in some way?
this takes list (looong) of everything produced before this putCharM and concatenates c as last member; this takes time linear in the length of the list, summing over all putCharMs it is quadratic (and of course, due to laziness a lot of memory is consumed; seq does not help, as it only evaluates first cell of the list so that it sees it is not empty; deepSeq would solve this, but the time consumption would still stay long). the second way:
M f >>= k = M $
let (x, o) = f
M f2 = k x
(x', o') = f2
in (x', o ++ o')
concatenate output of f (short) with output of f2 (the rest of computation,
i.e. looong); but the time is proportional to the length of first list,
so it is constant in our case; summing it over all putCharMs, we get linear
time and we are happy :-)
If you want to do it the first way, define
putCharM c = M $ \o -> ((), c : o)
and then reverse the list in runM.
Zdenek Dvorak
_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
