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')
this is done reverse way (because >>= is bracketed to the right); we 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