[Haskell-beginners] Is foldr slow?

[Daniel Fischer]

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
> recursion.

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 
the code.

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