Last update November 15, 2003

# DWiki / fold

A function that takes a collection, an initial value, a reduce operation and return a value resulting from the folding of the operation over the collection, starting from the initial value. If the collection is empty the initual valued passed is returned. Usually used with lists, but may be used with any kind of collection. There are two ways of folding: left-associative folds (foldl) and right-associative folds (foldr).

``` foldl([1, 2, 3, 4], 0, +),              becomes
foldl([2, 3, 4], 0 + 1, +),             becomes
foldl([3, 4], (0 + 1) + 2, +),          becomes
foldl([4], ((0 + 1) + 2) + 3, +),       becomes
foldl([], (((0 + 1) + 2) + 3) + 4, +),  becomes
(((0 + 1) + 2) + 3) + 4

foldr([1, 2, 3, 4], 0, +),              becomes
1 + foldr([2, 3, 4], 0, +),             becomes
2 + (1 + foldr([3, 4], 0, +)),          becomes
3 + (2 + (1 + foldr([4], 0, +))),       becomes
4 + (3 + (2 + (1 + foldr([], 0, +)))),  becomes
4 + (3 + (2 + (1 + 0)))

```
Using /DeimosTemplateLibrary:

```    instance TFunctionalArrays(int, int) arrays;
const int[] numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
int plus(int x, int y) { return x + y;};
int times(int x, int y) { return x ☆ y;};
int sum = arrays.foldl(numbers, 0, plus);
int product = arrays.foldr(numbers, 1, times);

```

(From DWiki)
| | | | | | | | | |

(date of last change: November 15, 2003 5:35 )