[Haskell-beginners] Factorials using foldx
daniel.is.fischer at web.de
Thu Aug 7 11:16:47 EDT 2008
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
facl will build a thunk of the form
(...(((1 * 1) * 2) * 3) * ...) * n, which will also blow the stack if n is
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
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
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
More information about the Beginners