[Haskell-beginners] Is foldr slow?
daniel.is.fischer at googlemail.com
Sun Feb 5 14:25:29 CET 2012
On Sunday 05 February 2012, 11:33:35, Zhi-Qiang Lei wrote:
> Thank you very much. You are right. foldl performs much better here. I
> thought foldr always has a performance advantage due to its tail
Firstly, tail recursion isn't automatically better in Haskell. Due to
laziness, the evaluation sequence is different from what it'd be in eager
languages, and not necessarily the order in which the steps are written in
If the recursive call to a (non tail-recursive) function is in a lazy
argument position of the result, a lot of evaluation can take place before
the recursive call is demanded.
A tail recursive function on the other hand cannot deliver any part of the
result before the recursion is completed.
Secondly, foldr is not tail recursive, foldl is:
foldr f z (x:xs) = x `f` (foldr f z xs)
foldl f z (x:xs) = foldl f (f z x) xs
Thus if 'f' is lazy in its second argument, like for example (++), the
result can be partially delivered before the recursive call, in
x ++ (foldr (++)  xs)
the whole list x has to be evaluated before the evaluation of foldr takes
its next step.
But if 'f' is strict in its second argument, like for example (+) on Int,
the recursive call has to be evaluated before the top level call to 'f' can
be evaluated, so a stack of function calls has to be built before any
evaluation of an 'f'-call can start, and that stack has to be unwound
during the evaluation of the 'f'-calls from the innermost to the outermost.
That gives you two traversals: build stack, unwind.
In such cases, tail recursion (a left fold) is better because then the call
to 'f' can be evaluated before the recursive call - but it has to be
forced, or it will generate a thunk ((...(z `f` x1) ... ) `f` xn-1) `f` xn
(and when that thunk is finally evaluated it nuilds a stack of 'f'-calls,
which is then unwound, so you get three traversals: build thunk, thunk ->
stack, unwind - unless 'f' is lazy in its first argument, like flip (++),
then the thunk may be consumed without building the stack).
> On Feb 3, 2012, at 5:36 AM, Chaddaï Fouché wrote:
> > let go a b = b `minus` (multiplies a c)
> > foldr go cs' (p:p':ps) ==> foldr go cs' (p':ps) `minus` multiplies p c
> > ==> (minus needs his first argument to start removing stuff) (foldr go
> > cs' ps `minus` multiplies p' c) `minus` multiplies p c
> > And so on and so forth...
> > In other words, contrary to your first version, this function must
> > develop the entire list before making its first suppression...
> > Your version rather correspond to a foldl (be careful of strictness,
> > using foldl it's pretty easy to get big thunks).
> > Foldr is very useful for functions that are lazy in their second
> > argument like (||) , (&&), (:) or others but if the function is
> > strict in its second argument like yours (strict in b)...
> Best regards,
> Zhi-Qiang Lei
> zhiqiang.lei at gmail.com
More information about the Beginners