[Haskell-cafe] How to write fast for loops

Bertram Felgenhauer 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 ())
>   where
>     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 mailing list