Fold

Context

Suppose you want to find the sum of the elements of a collection. You might write some code like this:

def input = [3, 5, 7, 9, 11, 13, 15, 17]

var accumulator := 0

for (input) do { each → 
    accumulator := accumulator + each 
}

This leaves the sum in the variable accumulator.

If instead you wanted to compute the product, you might write:

var accumulator := 1

for (input) do { each → 
    accumulator := accumulator * each 
}

If you wanted to concatenate the strings in a collection, you might write:

var accumulator := ""

for (input) do { each → 
    accumulator := accumulator ++ each 
}

This code pattern is very common; it’s called the accumulator pattern. You probably noticed that these examples were quite similar to each other. In fact, the only differences are

1. the operation that is applied to the accumulator and each element — addition, multiplication, and concatenation
2. the initial value of the accumulator — 0, 1 and the empty string.

What is fold?

The method fold (op) startingWith (initial) captures this pattern. fold(_)startingWith(_) is defined on all collections, including strings, sequences, lists and sets. The first argument is a block with two parameters; it is a block that describes the operation to be performed on the accumulator and the elements. The second argument is the initial value of the accumulator.

Let’s re-write our three examples using fold:

Understanding fold

The general pattern for using fold is as follows:

«collection».fold { «a», «b» → 
    «function»
} startingWith («initialValue»)

where «collection» is an expression that evaluates to any collection, «a» and «b» are any names you choose for the accumulator and the current element, and «function» is some Grace code, normally using the variables that you chose for «a» and «b». «initialValue» is the initial value of the accumulator.

Another way of thinking about folds, especially useful when the combining function can be written as an operator like *, is that it replaces the commas in the list by the operator. So fold { acc, each → acc * each } startingWith 1 transforms list [3, 5, 7, 9, 11, 13, 15, 17] into 1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17.

Fold on Sets

Notice that we said that fold(_)startingWith(_) is defined on sets. This is true even though sets have no defined ordering. Consequently, the order in which the elements are folded is indeterminate. This doesn’t matter for operations like + and *, which are themselves commutative. For an operation like ++, which is not commutative, the result of the fold with be concatenation in an arbitrary order.