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

Question

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 ?

Answer 1

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 specific 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:

• A tutorial on the universality and expressiveness of fold
• Writing foldl in terms of foldr
• On folds

Answer 2

Lots And Lots Of foldLeft Examples lists the following functions:

• sum
• product
• count
• average
• last
• penultimate
• contains
• get
• to string
• reverse
• unique
• to set
• double
• insertion sort
• pivot (part of quicksort)
• encode (count consecutive elements)
• decode (generate consecutive elements)
• group (into sublists of even sizes)

Answer 3

My lame answer is that:

• foldr is for reducing the problem to the primitive case and then assembling back up (behaves as a non tail-recursion)
• foldl is for reducing the problem and assembling the solution at every step, where at the primitive case you have the solution ready (bahaves as a tail recursion / iteration)

This question reminded me immediately of a talk by Ralf Lämmel Going Bananas (as the rfold operator notation looks like a banana (| and |)). There are quite illustrative examples of mapping recursion to folds and even one fold to the other.

The classic paper (that is quite difficult at first) is Functional Programming with Bananas, Lenses,. Envelopes and Barbed Wire named after the look of other operators.