Fold

Overview

Suppose separate loops compute an order list's total, count, and largest order. Each has the shape var acc = seed; foreach (var x in items) acc = step(acc, x);, differing only in its initial value and update rule. Yet every loop repeats the same skeleton and makes its own decision about what an empty list should return.

A fold packages that skeleton into one function, taking an initial value, or seed, and a combining function, or step. The initial value is the result before any element has been seen and the input to the first step; the combining function uses the result so far and the next element to produce a new result. That intermediate result is the accumulator. In C#, LINQ Aggregate performs this job.

Folding also applies to recursive structures such as trees. A handler for each kind of node combines the already-folded children into the parent's value.

Flow

With the same elements and seed, a left fold gives ((0 - 1) - 2) - 3 = -6, while a right fold gives 1 - (2 - (3 - 0)) = 2. For an operation such as subtraction, grouping changes the result, so the direction matters.

History

In his 1999 tutorial, Hutton describes fold, or foldr, as a standard operator capturing a common recursive pattern for processing lists. He traces its origins to recursion theory (Kleene, 1952), citing APL's reduction operator (Iverson, 1962) and FP's insertion operator (Backus, 1978) as examples of its central role in programming languages.¹

In that account, fold f v replaces the empty list at the end with v and each cons constructor with f. Hutton emphasizes the universal property as a tool for definitions and proofs: over finite lists, fold f v is the unique function satisfying g [] = v and g (x : xs) = f x (g xs). He also notes that foldl can be defined with fold, but the reverse definition is impossible because foldl is strict in the list's tail.²

Meijer, Fokkinga, and Paterson's 1991 paper calls such a function a catamorphism, from the Greek preposition meaning "down," and writes it with banana brackets (| |). The paper extends the same recursion operator from lists to algebraic data types in general.³

Why use it?

The fold owns the traversal skeleton, leaving the calculation in a combining function that accepts just an accumulator and one element. That small function is easy to name and test; when several summary values are needed, a record accumulator can compute them in one pass.

LINQ Sum, Count, Min, Max, and Average can be viewed as common aggregations with their seeds and combining rules already chosen. Microsoft's documentation describes them as standard query operators that simplify common aggregations. Use Aggregate directly when the accumulator cannot be expressed through one of those dedicated operators.⁴

Aggregate consumes the traversal provided by the Iterator Pattern all the way to a single value, beginning enumeration when it is called. Select and Where use deferred execution; an aggregation over a sequence that never ends will not finish.⁵

For subtraction or another operation whose result depends on grouping, the caller must choose the fold direction. The Monoid article covers structures that combine associativity, which makes grouping irrelevant, with an identity value suitable for the seed.

With a seed, the result for an empty sequence is that seed. The seedless Aggregate overload instead uses the first element as its initial accumulator, so an empty sequence causes InvalidOperationException.⁶

Readability and cost still matter. Hutton notes that a fold can be harder to read than explicit recursion, and an ordinary foreach is often clearer when the combining function becomes long. Copying the whole accumulator at every step can also make the total work quadratic. For (acc, s) => acc + s, each new string copies everything accumulated so far: joining 1,000 single-character strings produces intermediate strings with a combined length of 1 + 2 + ... + 1,000 = 500,500 characters. Use StringBuilder as the accumulator, or string.Concat or string.Join, for that case. Rebuilding an array to append each element has the same problem.¹

Example

Fold [1, 2, 3] from the left and right with the same seed. Having the combining function build a string shows the grouping directly. LINQ has no right-fold operator, so FoldRight is defined here; the argument order is (acc, x) for Aggregate and (x, acc) for FoldRight.

using System;
using System.Collections.Generic;
using System.Linq;

int[] numbers = [1, 2, 3];

// Aggregate is a left fold, updating the accumulator from the first element onward.
string leftText = numbers.Aggregate("0", (acc, x) => $"({acc} - {x})");
int left = numbers.Aggregate(0, (acc, x) => acc - x);
// LINQ has no right fold, so define one that works back from the end.
string rightText = FoldRight(numbers, "0", (x, acc) => $"({x} - {acc})");
int right = FoldRight(numbers, 0, (x, acc) => x - acc);
Console.WriteLine($"left:  {leftText} = {left}");
Console.WriteLine($"right: {rightText} = {right}");

// Concatenation gives the same result with either grouping.
string[] letters = ["a", "b", "c"];
string leftConcat = letters.Aggregate("", (acc, s) => acc + s);
string rightConcat = FoldRight(letters, "", (s, acc) => s + acc);
Console.WriteLine($"concat: {leftConcat} / {rightConcat}");

// Right fold: combine the final element with the seed, then work toward the front.
static TAcc FoldRight<T, TAcc>(IReadOnlyList<T> items, TAcc seed, Func<T, TAcc, TAcc> step)
{
    TAcc acc = seed;
    for (int i = items.Count - 1; i >= 0; i--) acc = step(items[i], acc);
    return acc;
}

left:  (((0 - 1) - 2) - 3) = -6
right: (1 - (2 - (3 - 0))) = 2
concat: abc / abc

Subtraction gives -6 or 2 depending on direction, while concatenation gives abc both ways.

A broader example

The first part summarizes orders with one Aggregate. Its accumulator, the immutable Summary record, holds the count, quantity, total, and largest order, with Summary.Empty as the seed. An empty list shows the differences between seeded aggregation, seedless Aggregate, Max, and Sum.

The second part folds an expression tree built from Num, Add, and Mul records. Fold takes a handler for each node kind and builds a parent result from the folded children, so changing the handlers lets the same traversal evaluate the expression, print it, or measure its depth. Replacing a data type's constructors with handlers in this way is a catamorphism.

using System;
using System.Collections.Generic;
using System.Linq;

Order[] orders =
[
    new("A-1", 2, 15_000m),
    new("A-2", 1, 42_000m),
    new("A-3", 3, 8_000m),
];
Order[] none = [];

// One Aggregate computes count, quantity, total, and the largest order.
Console.WriteLine(orders.Aggregate(Summary.Empty, Summary.Include));
Console.WriteLine(none.Aggregate(Summary.Empty, Summary.Include));

// Empty input: seedless Aggregate and Max throw, while Sum returns 0.
Report("Aggregate(no seed)", () => none.Select(o => o.Amount).Aggregate((a, b) => a + b));
Report("Max", () => none.Max(o => o.Amount));
Report("Sum", () => none.Sum(o => o.Amount));

// Expression-tree fold: take one handler for each constructor.
Expr expr = new Mul(new Add(new Num(2), new Num(3)), new Num(4));
int value = Fold(expr, n => n, (l, r) => l + r, (l, r) => l * r);
string text = Fold(expr, n => n.ToString(), (l, r) => $"({l} + {r})", (l, r) => $"{l} * {r}");
int depth = Fold(expr, _ => 1, (l, r) => 1 + Math.Max(l, r), (l, r) => 1 + Math.Max(l, r));
Console.WriteLine($"{text} = {value}, depth {depth}");

static void Report(string label, Func<decimal> run)
{
    try
    {
        Console.WriteLine($"{label}: {run()}");
    }
    catch (InvalidOperationException ex)
    {
        Console.WriteLine($"{label}: {ex.GetType().Name}: {ex.Message}");
    }
}

// C# lacks closed sum types, so a final arm is required.
static T Fold<T>(Expr e, Func<int, T> num, Func<T, T, T> add, Func<T, T, T> mul) => e switch
{
    Num n => num(n.Value),
    Add a => add(Fold(a.Left, num, add, mul), Fold(a.Right, num, add, mul)),
    Mul m => mul(Fold(m.Left, num, add, mul), Fold(m.Right, num, add, mul)),
    _ => throw new ArgumentOutOfRangeException(nameof(e), e, "unknown node"),
};

sealed record Order(string Id, int Quantity, decimal UnitPrice)
{
    public decimal Amount => Quantity * UnitPrice;
}

// The accumulator is an immutable summary of the orders seen so far.
sealed record Summary(int Count, int Quantity, decimal Total, Order? Largest)
{
    public static readonly Summary Empty = new(0, 0, 0m, null);

    public static Summary Include(Summary acc, Order o) => new(
        acc.Count + 1,
        acc.Quantity + o.Quantity,
        acc.Total + o.Amount,
        acc.Largest is null || o.Amount > acc.Largest.Amount ? o : acc.Largest);

    public override string ToString() =>
        $"orders={Count} qty={Quantity} total={Total} largest={Largest?.Id ?? "(none)"}";
}

abstract record Expr;
sealed record Num(int Value) : Expr;
sealed record Add(Expr Left, Expr Right) : Expr;
sealed record Mul(Expr Left, Expr Right) : Expr;

orders=3 qty=6 total=96000 largest=A-2
orders=0 qty=0 total=0 largest=(none)
Aggregate(no seed): InvalidOperationException: Sequence contains no elements
Max: InvalidOperationException: Sequence contains no elements
Sum: 0
(2 + 3) * 4 = 20, depth 3

Summary creates a record per element and keeps the earlier order when amounts tie. The expression-tree Fold is recursive, using call-stack space proportional to tree depth. In the recorded .NET 10 run, the same Fold handled an Add tree of depth 1,000 but overflowed the default stack and terminated the process at depth 1,000,000. StackOverflowException cannot be caught with try/catch, so trees whose depth grows with input need an explicit-stack iteration or a depth limit. C# also lacks closed sum types: the switch needs a final _ arm, which prevents the compiler from warning about an unhandled new node type.⁷

TypeScript example

JavaScript arrays provide reduce for a left fold and reduceRight for a right fold. Calling reduce on an empty array without a seed fails as Aggregate does in C#, but with TypeError. The expression tree uses a discriminated union distinguished by kind, letting the compiler recognize an exhaustive switch over the three cases without the final arm needed in C#.

const numbers = [1, 2, 3];

// reduce is a left fold; reduceRight is a right fold.
const leftText = numbers.reduce((acc, x) => `(${acc} - ${x})`, "0");
const rightText = numbers.reduceRight((acc, x) => `(${x} - ${acc})`, "0");
console.log(`left:  ${leftText} = ${numbers.reduce((acc, x) => acc - x, 0)}`);
console.log(`right: ${rightText} = ${numbers.reduceRight((acc, x) => x - acc, 0)}`);

// Empty array: no seed causes TypeError; a seed becomes the result unchanged.
const empty: number[] = [];
try {
  console.log(empty.reduce((a, b) => a + b));
} catch (e) {
  if (!(e instanceof TypeError)) throw e;
  console.log(`no seed: ${e.name}: ${e.message}`);
}
console.log(`seed 0: ${empty.reduce((a, b) => a + b, 0)}`);

type Expr =
  | { kind: "num"; value: number }
  | { kind: "add"; left: Expr; right: Expr }
  | { kind: "mul"; left: Expr; right: Expr };

// Expression-tree fold: take one handler for each constructor.
function fold<T>(e: Expr, num: (v: number) => T, add: (l: T, r: T) => T, mul: (l: T, r: T) => T): T {
  switch (e.kind) {
    case "num": return num(e.value);
    case "add": return add(fold(e.left, num, add, mul), fold(e.right, num, add, mul));
    case "mul": return mul(fold(e.left, num, add, mul), fold(e.right, num, add, mul));
  }
}

const n = (value: number): Expr => ({ kind: "num", value });
const expr: Expr = { kind: "mul", left: { kind: "add", left: n(2), right: n(3) }, right: n(4) };
const value = fold(expr, (v) => v, (l, r) => l + r, (l, r) => l * r);
const text = fold(expr, (v) => String(v), (l, r) => `(${l} + ${r})`, (l, r) => `${l} * ${r}`);
console.log(`${text} = ${value}`);

left:  (((0 - 1) - 2) - 3) = -6
right: (1 - (2 - (3 - 0))) = 2
no seed: TypeError: Reduce of empty array with no initial value
seed 0: 0
(2 + 3) * 4 = 20

reduceRight still puts the accumulator first in the callback, so right-fold subtraction explicitly reverses the operands with (acc, x) => x - acc. As in C#, the tree fold is recursive and uses stack space proportional to depth.

See also

• Functional Programming

• Programming Patterns

• Monoid

• Iterator Pattern

Example environment: each C# example is a separate .NET 10 console program; compile TypeScript for ES2022 or later, then run the JavaScript with Node.js.