Running out of memory in a simple monad

[Zdenek Dvorak]

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