Am Donnerstag, 7. August 2008 16:16 schrieb Paul Johnston:
Hi (First question so be gentle)! Just started to look at Haskell and I was wondering about various versions of calculating factorials.
If I have
facr 0 = 1 facr n = foldr (*) 1 [1..n]
facl 0 = 1 facl n = foldl (*) 1 [1..n]
Is there any difference in efficiency, I remember reading it is better to count down than to count up but left to right or right to left :-)
For this task, there will be no big difference unless the compiler's optimiser sees the strictness (which it can, if the type is appropriately determined). facr will build a thunk of the form 1 * (2 * (3 * (4 * (... * (n * 1) ...)))), there is no way the evaluation can start before the end of the list is reached, so the size of the thunk is O(n) and it will blow the stack if n is too large. facl will build a thunk of the form (...(((1 * 1) * 2) * 3) * ...) * n, which will also blow the stack if n is large enough. Since it is built from the inside out, it could be evaluated in each step to prevent the stack overflow, but because of the laziness, that will only happen if the implementation knows that it will be needed, which is for instance the case if you compile with -O (at least if you use GHC) and the type of facl can be deduced or is given as Int -> Int or Integer -> Integer. You can get that behaviour without relying on the optimiser by using the strict left fold foldl' from Data.List, which forces evaluation at each step. As a general rule, if you can get a result (or start producing a result) without traversing the entire list, use foldr. Examples for this are and = foldr (&&) True and or = foldr (||) False and for the case of producing partial results concat = foldr (++) []. If you need to consume the entire list to get a result, use foldl'. I don't know of any case where foldl is a better choice than foldl'.
Cheers Paul
Cheers, Daniel