[Haskell-beginners] Factorials using foldx

[Tillmann Rendel]

ajb at spamcop.net wrote:
> There's one more possibility you should be aware of, assume you're
> trying to compute large factorials, and that's to use a binary
> tree-style recursion pattern.  This one is bottom-up, but you could
> also do top-down:

Here's my top-down binary fold, with growing tree sizes to allow the 
processing of infinite lists.

   module Binfold where

   import System.Environment
   import Data.List

   -- fold the first 2 ** n elements tree-shaped
   binfold :: Int -> (a -> a -> a) -> a -> [a] -> (a, [a])
   binfold n f i [] = (i, [])
   binfold 0 f i (x:xs) = (x, xs)
   binfold n f i xs = (f y z, xs'') where
     (y, xs') = binfold (pred n) f i xs
     (z, xs'') = binfold (pred n) f i xs'

   -- fold with a growing sequence of binfolds
   growfold :: Int -> (a -> a -> a) -> a -> [a] -> a
   growfold n f i [] = i
   growfold n f i xs = f y (growfold (succ n) f i xs') where
     (y, xs') = binfold n f i xs

   main = do
     [op, n] <- getArgs
     let fold = case op of
                  "growfold" -> growfold 0
                  "foldr" -> foldr
                  "foldl" -> foldl
                  "foldl!" -> foldl'
     print . length . show . fold (*) 1 . enumFromTo 1 . read $ n


$ ghc -O2 -main-is Binfold -o Binfold Binfold.hs
$ time ./Binfold foldr 100000
456574

real    0m15.094s
user    0m0.015s
sys     0m0.031s

$ time ./Binfold foldl 100000
456574

real    0m18.000s
user    0m0.030s
sys     0m0.015s

$ time ./Binfold foldl! 100000
456574

real    0m4.641s
user    0m0.031s
sys     0m0.031s

$ time ./Binfold growfold 100000
456574

real    0m0.954s
user    0m0.015s
sys     0m0.015s

   Tillmann