Fold functions

A fold (also commonly called reduce) processes an input data structure in some order to build up an output value.

Inputs:

  • A function to combine the elements of the data structure
  • A starting value
  • A data structure

For lists, which have two simple directions of ordering, this looks like (right and left):

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr + 0 [1..5] = 1 + (2 + (3 + (4 + (5 + 0))))
foldl :: (a -> b -> a) -> a -> [b] -> a

foldl + 0 [1..5] = ((((0 + 1) + 2) + 3) + 4) + 5

Implemented in terms of each other,

foldr f b as = foldl (\g a x -> g (f a x)) id as b

foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

When to use right and left

  • Depends on the associativity of the function you are folding with
  • Foldr is like recursion
  • Foldl is like iteration

Lazy languages e.g. Haskell

  • A right fold will pass the intermediate value to
logo