Folding

A functional iterator is a function that traverses a data structure and calls in turn a given function over the elements of that structure to compute some value. Another approach is sometimes possible: loops.

There are three kinds of functional iterations over sets: the fold, the map (not to be confused with the map data structure) and the iteration.

Let us consider first here the fold, which is the most general form of functional iteration. The folded function takes two arguments: an accumulator and the structure element at hand, with which it then produces a new accumulator. This enables having a partial result that becomes complete when the traversal of the data structure is over.

The function Set.fold performs a fold over a set, in increasing order of its elements. The function Set.fold_desc folds in decreasing order. The different in their types is the type of the folded operation: with Set.fold, that function takes the accumulator first, whereas with Set.fold_desc, the accumulator comes second.

const s : set<int> = Set.literal([1, 2, 3]);

// incr == [3, 2, 1]

const incr : list<int> = Set.fold (([a,i]) => ([i,...a] as list<int>), s, []);

// decr == [1, 2, 3]

const decr : list<int> = Set.fold_desc (([i,a]) => ([i,...a] as list<int>), s, []);

Note: See the predefined namespace Set