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
Just to add to what Zdenek wrote: The linear complexity of string concatenation in a naïve implementation (not having access to an extra-language "end-of-list" in the "diff list" sense...) make the total complexity O(n^2), since the number of conses generated is thus sum [1 .. n] which, obviously, is (1+n)*n/2. In the case of the n=50000 in the example we get "sum [1 .. 50000]" => "1250025000". So, well over one billion conses. This is why "++" is right associative :-) This time complexity cannot make Hugs crash, though, except for a defect GC, having problems tidying up after each round of "++". The space complexity, which reduces to maximum execution stack space (considering a proper GC) in the example, is what kills Hugs. The problem is that the string concatenation is not the last call, so there is no room for last call optimization. If you want to mimic the complexity of the example while calculating the number of conses required, try evaluating the "isomorphic" expression last $ scanl1 (+) $ take 50000 (repeat 1) It might crash in Hugs, running out of execution stack space, for the same reason as the original example. It is the "last" that holds up the stack space, by the way. I hope this was helpful. Regarding "do": It is easy to get the feeling that the recursive call in recurse = do f x recurse is the last one, but this is just an illusion of the iterative layout of "do". Sometimes the monads lure us into old iterative thought patterns... Taking away the syntactic sugar, we end up with recurse = f x >> recurse This reveals the fact that there can be no last call optimization, because the last call is ">>". Regards, David
participants (2)
-
David Bergman -
Zdenek Dvorak