gistfile1.hs

{-

foldc - "fold centre"

Perfoms a fold of a list, given an associative operation, in a binary-tree pattern.

For example, folding the numbers 1 through 10 with the operation * looks like this:

foldl1: (((((((((1 * 2) * 3) * 4) * 5) * 6) * 7) * 8) * 9) * 10)
foldr1: (1 * (2 * (3 * (4 * (5 * (6 * (7 * (8 * (9 * 10)))))))))
foldc1: ((((1 * 2) * (3 * 4)) * ((5 * 6) * (7 * 8))) * (9 * 10))

The maximum depth of the resulting expression tree is linear in the length of the
list for foldl and foldr, but logarithmic for foldc. For certain operations, this
makes foldc much faster.

Consider Data.Map.unions applied to disjoint maps: the time taken to fully evaluate
a `union` b is proportional to size a + size b. With the standard implementation of
"unions" as "foldl union", the runtime is O(n * n * m) where m is the average length
of a list and n is the number of lists (since unions [a,b,c,...] is ((a + b) + c)...,
the early maps are traversed up to n times).

If unions is implemented as "foldc union", the runtime shrinks to O(n * log n * m).

-}


foldc1 :: (a -> a -> a) -> [a] -> a
foldc1 f [] = error "foldc1 called with empty list"
foldc1 f (x:xs) = bigfold x xs 0
    where
      bigfold x xs n =
          case (fold xs n) of
            (r, []) -> x `f` r
            (r, l) -> bigfold (x `f` r) l (n+1)

      fold (x:xs) 0 = (x,xs)
      fold xs n = 
          case (fold xs (n-1)) of
            (p, []) -> (p, [])
            (p, ps) -> let (q,qs) = fold ps (n-1) in (p `f` q, qs)

foldc f z [] = z
foldc f z x = foldm1 f x