[Haskell-cafe] How to write fast for loops
bertram.felgenhauer at googlemail.com
Tue Apr 29 13:03:54 UTC 2014
Daniel Trstenjak wrote:
> Regarding the used stack space, wouldn't the following solution be even better?
> forLoop :: (Monad m) => a -> (a -> Bool) -> (a -> a) -> (a -> m ()) -> m ()
> forLoop start cond inc f = go start (return ())
> go !x m | cond x = go (inc x, m >> f x)
> | otherwise = m
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. 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.
More information about the Haskell-Cafe