6.2 Reductions and folding a collection from many items to one

We can consider the sum() function to have the following kind of definition. We could say that the sum of a collection is 0 for an empty collection. For a non-empty collection, the sum is the first element plus the sum of the remaining elements:

We can use a slightly simplified notation called the Bird-Meertens Formalism. This uses ⊕∕[c₀,c₁,...c_n] to show how some arbitrary binary operator, ⊕, can be applied to a sequence of values. It’s used as follows to summarize a recursive definition into something a little easier to work with:

We’ve effectively folded the + operator between each item of the sequence. Implicitly, the processing will be done left to right. This could be called a ”fold left” way of reducing a collection to a single value. We could also imagine grouping the operators from right to left, calling this a ”fold right.” While some compiled...