[Haskell-cafe] How to write fast for loops
daniel.trstenjak at gmail.com
Tue Apr 29 15:29:26 UTC 2014
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?
> 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.
More information about the Haskell-Cafe