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:
![(| { 0 if n = 0 sum ([c0,c1,c2,...,cn]) = | ( c0 + sum ([c1,c2,...,cn]) if n > 0](https://static.packt-cdn.com/products/9781803232577/graphics/Images/file54.jpg)
We can use a slightly simplified notation called the Bird-Meertens Formalism. This uses ⊕∕[c0,c1,...cn] 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:
![sum ([c0,c1,c2,...,cn]) = + ∕[c0,c1,c2,...,cn] = 0+ c0 + c1 + ...+ cn](https://static.packt-cdn.com/products/9781803232577/graphics/Images/file55.jpg)
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...
