Fold (higher-order function)
From Wikipedia, the free encyclopedia
In functional programming, fold (or reduce) is a family of higher-order functions that process a data structure in some order and build up a return value. This is as opposed to the family of unfold functions which take a starting value and apply a function to it repeatedly to generate a data structure. Typically, a fold deals with two things: a combining function, and a data structure, typically a list of elements. The fold then proceeds to combine elements of the data structure using the function in some systematic way. For instance, we might write
fold (+) [1,2,3,4,5]
which would result in 1 + 2 + 3 + 4 + 5, which is 15. In this instance, + is an associative operation so it is irrelevant how one parenthesizes the addition. To a rough approximation, you can think of the fold as replacing the commas in the list with the + operation.
However, in the general case, functions of two parameters are not associative, so the order in which one carries out the combination of the elements matters. On lists, there are two obvious ways to carry this out: either by recursively combining the first element with the results of combining the rest (called a right fold) or by recursively combining the results of combining all but the last element with the last one, (called a left fold). Also, in practice, it is convenient and natural to have an initial value which in the case of a right fold, is used when one reaches the end of the list, and in the case of a left fold, is what is initially combined with the first element of the list. This is perhaps clearer to see in the equations defining foldr and foldl in Haskell. Note that in Haskell, [] represents the empty list, and (x:xs) represents the list starting with x and where the rest of the list is xs.
foldr f z [] = z
-- if the list is empty, the result is the initial value z
foldr f z (x:xs) = f x (foldr f z xs)
-- if not, apply f to the first element and the result of folding the rest
foldl f z [] = z
-- if the list is empty, the result is the initial value
foldl f z (x:xs) = foldl f (f z x) xs
-- if not, we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
One important thing to note in the presence of lazy, or normal-order evaluation, is that foldr will immediately return the application of f to the recursive case of folding over the rest of the list. Thus, if f is able to produce some part of its result without reference to the recursive case, and the rest of the result is never demanded, then the recursion will stop. This allows right folds to operate on infinite lists. By contrast, foldl will immediately call itself with new parameters until it reaches the end of the list. This tail recursion can be efficiently compiled as a loop, but can't deal with infinite lists at all -- it will recurse forever in an infinite loop. Another technical point to be aware of in the case of left folds in such languages is that the new initial parameter is not being evaluated before the recursive call is made. This can lead to stack overflows when one reaches the end of the list and tries to evaluate the resulting potentially gigantic expression. For this reason, such languages often provide a stricter variant of left folding which forces the evaluation of the initial parameter before making the recursive call, in Haskell, this is the foldl' (note the apostrophe, pronounced 'prime') function in the Data.List library. Combined with the speed of tail recursion, such folds are very efficient when lazy evaluation of the final result is impossible or undesirable.
One often wants to choose the identity element of the operation f as the initial value z. When no initial value seems appropriate, for example, when one wants to fold the function which computes the maximum of its two parameters over a list in order to get the maximum element of the list, there are variants of foldr and foldl which use the last and first element of the list respectively as the initial value. In Haskell and several other languages, these are called foldr1 and foldl1, the 1 making reference to the automatic provision of an initial element, and the fact that the lists they are applied to must have at least one element.
In Scheme, right and left fold can be written as:
(define (foldr f z xs)
(if (null? xs)
z
(f (car xs) (foldr f z (cdr xs)))))
(define (foldl f z xs)
(if (null? xs)
z
(foldl f (f z (car xs)) (cdr xs))))
The C++ Standard Template Library implements left fold as the function "accumulate" (in the header <numeric>).
[edit] Another approach
Folds can be viewed as a mechanism for replacing the structural components of a data structure with functions and values in a regular way. In many languages, lists are built up from two primitives: any list is either the empty list, commonly called nil, or it is a list constructed by appending an element to the start of some other list, which we call a cons. In Haskell, the cons operation is written as a colon (:), and in Scheme and other lisps, it is called cons. One can view a right fold as substituting the nil at the end of the list with a specific value, and each cons with a specific other function. Hence, one gets a diagram which looks something like this:
In the case of a left fold, the structural transformation being performed is somewhat less natural, but is still quite regular:
These pictures do a rather nice job of motivating the names left and right fold visually. It also makes obvious the fact that foldr (:) [] is the identity function on lists, as replacing cons with cons and nil with nil will not change anything. The left fold diagram suggests an easy way to reverse a list, foldl (flip (:)) []. Note that the parameters to cons must be flipped, because the element to add is now the right hand parameter of the combining function. Another easy result to see from this vantage-point is to write the higher-order map function in terms of foldr, by composing the function to act on the elements with cons, as:
map f = foldr ((:) . f) []
where the period (.) is an operator denoting function composition.
This way of looking at things provides a simple route to designing fold-like functions on other algebraic data structures, like various sorts of trees. One writes a function which recursively replaces the constructors of the datatype with provided functions, and any constant values of the type with provided values. Such a function is generally referred to as a catamorphism.
