Running out of memory in a simple monad

[Richard Uhtenwoldt]

David Bergman writes:

>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 ">>".

What do you mean by this?  Do you mean that that an implementation
cannot execute arbitrarily many iterations/recursions of that last
loop/definition in constant space?

If that's what you mean, you are wrong.  GHC does that.  The IO monad
would be pretty damned useless for actual work if implementations did
not do that!

Even if we replace the (>>) with a (:) as the "main operator"/"last
call" of the loop, the result can execute in constant space because
of optimizations.

E.g., the program

  loop n=n:loop (n+1)
  main = print (loop 0)

executes in constant space when compile by GHC 5.02.


Details: 

Specifically, I let it run till it printed 2,500,000 at which time top
reported the "RSS" to be 1,500 with no increase having occurred in a
long time.  top's manpage says that "RSS" is "the total amount of
physical memory used by the task, in kilobytes".

The statement about (>>) is true when the (>>) is in the IO monad.  I
did not check to see what happens in a "user-defined" monad.