Folds On Lists
The folding of the list with the addition operator would result in 15, the sum of the elements of the list . To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving 1 + 2 + 3 + 4 + 5.
In the example above, + is an associative operation, so the final result will be the same regardless of parenthesization, although the specific way in which it is calculated will be different. In the general case of non-associative binary functions, the order in which the elements are combined may influence the final result's value. On lists, there are two obvious ways to carry this out: either by combining the first element with the result of recursively combining the rest (called a right fold), or by combining the result of recursively combining all elements but the last one, with the last element (called a left fold). This corresponds to a binary operator being either right-associative or left-associative, in Haskell's or Prolog's terminology. With a right fold, the sum would be parenthesized as 1 + (2 + (3 + (4 + 5))), whereas with a left fold it would be parenthesized as (((1 + 2) + 3) + 4) + 5.
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. In the example above, the value 0 (the additive identity) would be chosen as an initial value, giving 1 + (2 + (3 + (4 + (5 + 0)))) for the right fold, and ((((0 + 1) + 2) + 3) + 4) + 5 for the left fold.
Read more about this topic: Fold (higher-order Function)
Famous quotes containing the words folds and/or lists:
“Bunched upside down, they sleep in air.
Their sharp ears, their sharp teeth, their quick sharp faces
Are dull and slow and mild.
All the bright day, as the mother sleeps,
She folds her wings about her sleeping child.”
—Randall Jarrell (1914–1965)
“Most of our platitudes notwithstanding, self-deception remains the most difficult deception. The tricks that work on others count for nothing in that very well-lit back alley where one keeps assignations with oneself: no winning smiles will do here, no prettily drawn lists of good intentions.”
—Joan Didion (b. 1934)