Zhi-Qiang Lei zhiqiang.lei at gmail.com
Mon Feb 6 17:42:09 CET 2012

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