Dive C2.05.2

From the accumulator loop to fold

One function aggregates a list any way you ask. The folder is all that changes.

The most common loop a C# developer writes is the same shape every time: declare an accumulator, walk the collection, combine each element into the accumulator, return it. That shape has a name in F# — List.fold — and the loop body that mutated the accumulator becomes a two-argument folder function acc -> x -> acc that fold applies at each element. Change the folder and the same call sums, finds a maximum, counts, or rebuilds the list. This dive shows fold as the one aggregator, its right-folding sibling foldBack, the seedless reduce, and the C# Aggregate it mirrors.

Run a fold Module hub

C2.05.2 · part 1

The loop, and the fold beside it

Take the sum loop. The C# version is a mutable total and a for. The F# version names the operation that combines a running total with the next element — addition — and the value to start from — zero. List.fold takes those two and the list, and walks it left to right, threading the result.

C# — the accumulator loop

int t = 0;
for (int i = 0; i < xs.Length; i++)
    t += xs[i];                   // combine each element into t
return t;                         // new[]{1,2,3,4,5} -> 15

F# — name the folder and the seed

// List.fold : folder -> state -> list -> state
List.fold (+) 0 [1..5]                       // val it : int = 15
List.fold (fun acc x -> acc + x) 0 [1..5]    // val it : int = 15

The two lines do the same thing. (+) is the folder written as the operator itself; (fun acc x -> acc + x) is the same folder written out, so its two arguments are visible: the running acc on the left, the next element x on the right. fold calls it once per element and feeds the result back in as the next acc — the loop body, made a value.

folder: a two-argument function acc -> x -> acc — the old loop body, applied at each element.
state: the seed the fold starts from — the accumulator's initial value (here 0).
fold: walks the list left to right, threading the accumulator; it is tail-recursive, so it does not grow the stack.

C2.05.2 · part 2

One fold, many aggregations

The reason fold earns its place is that the same call does any aggregation — the only thing that changes is the folder and the seed. Sum with (+) from 0; find the maximum with max from 0; count with (fun acc _ -> acc + 1) from 0; even rebuild the list with the cons operator :: from the empty list. Each echo below was produced by dotnet fsi.

let xs = [3; 1; 4; 1; 5]
List.fold (+) 0 xs                           // val it : int = 14   (sum)
List.fold max 0 xs                           // val it : int = 5    (maximum)
List.fold (fun acc _ -> acc + 1) 0 xs       // val it : int = 5    (count)
List.fold (fun acc x -> x :: acc) [] xs     // val it : int list = [5; 1; 4; 1; 3]  (rebuilt, reversed)

Two siblings round out the family. List.reduce is fold without a seed — it uses the first element as the starting accumulator, which is handy when the list is known to be non-empty and no natural seed exists. List.foldBack folds from the right: its argument order is folder list state (note the list comes before the seed), and the folder is x -> acc -> acc. Folding right is what you want when the combine order matters — rebuilding a list with :: via foldBack keeps the original order, where fold reverses it.

// reduce: fold with no seed (first element starts the accumulator)
List.reduce (+) [1..5]                        // val it : int = 15

// foldBack: folds right; args are (folder list state)
List.foldBack (fun x acc -> x + acc) [1..5] 0   // val it : int = 15
List.foldBack (fun x acc -> x :: acc) [1..5] []  // val it : int list = [1; 2; 3; 4; 5]  (order kept)

Reach for reduce only on a list you know is non-empty — List.reduce on [] raises ArgumentException. When the list may be empty, give fold a seed instead. For the everyday cases there are named shortcuts — List.sum, List.max, List.length — each a fold underneath.

Run a fold, element by element

Pick a folder and step the fold across the fixed list [3; 1; 4; 1; 5]. The accumulator box shows the running value; each Step consumes the next element, applies the folder, and updates it. The three folders are the verified ones above: (+) from 0 sums to 14, max from 0 lands on 5, and (fun acc x -> x :: acc) from [] rebuilds the list in reverse. The readout names the folder call at each step.

List.fold folder seed [3; 1; 4; 1; 5]

(+) · seed 0 · ready — acc = 0. Each Step folds the next element: 0+3, then +1, +4, +1, +5 → 14.

Without JavaScript: the three folds over [3; 1; 4; 1; 5], traced
folder · seed	accumulator after each element	fold result
`(+)` · 0	0 → 3 → 4 → 8 → 9 → 14	14
`max` · 0	0 → 3 → 3 → 4 → 4 → 5	5
`(fun acc x -> x :: acc)` · []	[] → [3] → [1;3] → [4;1;3] → [1;4;1;3] → [5;1;4;1;3]	[5; 1; 4; 1; 3]

One walk, one accumulator, one folder per problem. The aggregation a C# loop spelled out in its body is the argument you hand fold.

C2.05.2 · part 3

The same idea in C#: Aggregate

C# already has fold — LINQ calls it Aggregate. The seeded overload takes the starting value and a lambda (acc, x) => …, exactly the folder and seed of List.fold. A C# developer who has written .Aggregate(0, (acc, x) => acc + x) has already written a fold; F# makes it the default way to aggregate rather than the advanced one.

C# — LINQ Aggregate (seeded)

var sum = new[]{ 1, 2, 3, 4, 5 }
    .Aggregate(0, (acc, x) => acc + x);   // 15

F# — List.fold

// the same seed and the same combiner
List.fold (fun acc x -> acc + x) 0 [1..5]    // val it : int = 15
List.fold (+) 0 [1..5]                       // val it : int = 15

C# habit

A for loop with a mutable accumulator, or LINQ's Aggregate(seed, (acc, x) => …) when reaching for it.

F# form

List.fold folder seed list — the everyday aggregator, with foldBack, reduce, and named shortcuts alongside.

Where this leads

fold collapses a list into a single value. The other two workhorses keep the list a list: map transforms every element, filter keeps some, and choose does both. Those are the loops that build a new collection, and they are the next dive — the last of the three day-one habits to swap.

↑ C2.05 · From loops to recursion, map & fold ↩ C2.05.1 · From loops to recursion C2.05.3 · From the transform loop to map & filter →

References

Sources

Microsoft — F# lists — fold, foldBack, reduce on the List module.
FSharp.Core API reference — List.fold, List.foldBack, List.reduce, and the signatures and argument orders.
Microsoft — Enumerable.Aggregate — the LINQ fold, seeded and seedless.

Related in this course

C2.05.1 — From loops to recursion — the accumulator loop fold abstracts.
C1.07 — Collections: list, array, seq, Map & Set — the structures fold walks.
C1.03 — Functions, currying & partial application — the folder you hand to fold.