Tillmann Rendel rendel at daimi.au.dk
Fri Aug 8 06:24:44 EDT 2008

```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
```