On Tue, Apr 29, 2014 at 03:03:54PM +0200, Bertram Felgenhauer wrote:
This version would build a thunk of shape (return () >> f x1 >> ... before any of the f xi calls get a chance to run; to make matters worse, evaluating that thunk *will* use the evaluation stack.
Ok, I can see, that it has to build the whole thunk, because otherwise 'go' couldn't return anything. But why would the evaluation of the thunk use the stack? Why does the evaluation of '>>' in this case use the stack and in the other it doesn't?
The
go !x | cond x = f x >> go (inc x) | otherwise = return ()
version is better. The guideline here is the strictness of (>>): in most monads, (>>) is strict in its first argument but lazy in its second one; furthermore, the second argument is used at most once in typical monad stacks. So the evaluation stack is not used up at all: Evaluating 'go x' will suspend the 'go (inc x)' call while 'f x' is being run; once 'f x' returns, the 'go (inc x)' is taken care of, which is now effectively a tail call. Laziness saves the day.
I think that I was mostly irritated by 'mapM', which uses the stack, but that's because of it's use of '>>=', and it's bound value has to be kept on the stack. Thanks! Greetings, Daniel