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.