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 ?


  • 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.