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@gmail.com