functional-programmingfoldcatamorphism

# What are practical examples of the higher-order functions foldl and foldr?

The typical academic example is to sum a list. Are there real world examples of the use of fold that will shed light on its utility ?

Solution

• `fold` is perhaps the most fundamental operation on sequences. Asking for its utility is like asking for the utility of a `for` loop in an imperative language.

Given a list (or array, or tree, or ..), a starting value, and a function, the `fold` operator reduces the list to a single result. It is also the natural catamorphism (destructor) for lists.

Any operations that take a list as input, and produce an output after inspecting the elements of the list can be encoded as folds. E.g.

``````sum      = fold (+) 0

length   = fold (λx n → 1 + n) 0

reverse  = fold (λx xs → xs ++ [x]) []

map f    = fold (λx ys → f x : ys) []

filter p = fold (λx xs → if p x then x : xs else xs) []
``````

The fold operator is not speciﬁc to lists, but can be generalised in a uniform way to ‘regular’ datatypes.

So, as one of the most fundamental operations on a wide variety of data types, it certainly does have some use out there. Being able to recognize when an algorithm can be described as a fold is a useful skill that will lead to cleaner code.

References: