Running out of memory in a simple monad

[David Bergman]

Just to add to what Zdenek wrote:

The linear complexity of string concatenation in a na=EFve =
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=3D50000 in the
example we get "sum [1 .. 50000]" =3D> "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 =3D 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 =3D f x >> recurse

This reveals the fact that there can be no last call optimization,
because the last call is ">>".

Regards,

David