[Haskell-beginners] Is foldr slow?

[Zhi-Qiang Lei]

Appreciate. That's favorable to understand recursion in Haskell.

On Feb 5, 2012, at 9:25 PM, Daniel Fischer wrote:

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


Best regards,
Zhi-Qiang Lei
zhiqiang.lei at gmail.com