[Haskell-beginners] Factorials using foldx

[Daniel Fischer]

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