Recursion & Folds

You already know recursion: a function that calls itself on a smaller problem. In functional programming recursion isn't an occasional trick — it's the main way we repeat, because there are no mutable loop counters to lean on. The key insight is structural recursion: when your data is built out of smaller pieces of the same shape, your function follows that shape exactly.

A list is the perfect example. Think of it not as "a block of indexed slots" but as a recursive structure: a list is either empty, or a first item (the head) followed by a smaller list (the tail). Every list function then writes itself:

Structural recursion on a list

Here is \text{sum} and \text{length}, both following the very same skeleton — empty list is the base case, otherwise combine the head with the recursive result on the tail. Spot how identical their shape is.

function sum(xs: number[]): number { if (xs.length === 0) return 0; // base: empty sums to 0 const [head, ...tail] = xs; // split head / tail return head + sum(tail); // combine head with rest } function length(xs: number[]): number { if (xs.length === 0) return 0; // base: empty has length 0 const [, ...tail] = xs; return 1 + length(tail); // count this one, recurse on rest } console.log("sum:", sum([4, 8, 15, 16, 23, 42])); console.log("length:", length([4, 8, 15, 16, 23, 42]));

Two different jobs, one shape. When you notice yourself writing that skeleton over and over, it's a sign there's a pattern begging to be captured — and there is. It's called a fold.

The fold: recursion, captured once

A fold abstracts "walk a list, combining each item into a running result" — the exact pattern from reduce. You hand it a combining function and a starting value, and it does the recursion for you. Every function we just wrote by hand becomes a one-liner.

const xs = [4, 8, 15, 16, 23, 42]; const sum = xs.reduce((acc, x) => acc + x, 0); const length = xs.reduce((acc) => acc + 1, 0); const max = xs.reduce((acc, x) => Math.max(acc, x), -Infinity); const product = xs.reduce((acc, x) => acc * x, 1); console.log({ sum, length, max, product });

A fold has two ingredients — a combine function and a seed (the starting/identity value) — and that's precisely the base case and recursive case of the hand-written version. The fold is structural recursion over a list, written once and reused forever.

foldl versus foldr: which end do you start from?

There are two ways to fold, differing in direction:

For an operation like + that is associative and commutative, both give the same number. But the direction is visible the moment the operation cares about order — like subtraction, or building a list:

const xs = [1, 2, 3, 4]; // foldl: (((0 - 1) - 2) - 3) - 4 = -10 const left = xs.reduce((acc, x) => acc - x, 0); // foldr: 1 - (2 - (3 - (4 - 0))) = -2 const right = xs.reduceRight((acc, x) => x - acc, 0); console.log("foldl (reduce): ", left); console.log("foldr (reduceRight):", right);

foldl is usually the practical choice on real machines: it can run as a tight loop carrying one accumulator, using constant stack space. foldr is often more natural to reason about — it mirrors how the data is built and is the one that plays nicely with lazy, possibly-infinite lists (a story for the lazy-evaluation page). A neat fact: foldr with the "cons" (prepend) operation and an empty seed just rebuilds the list — which is why foldr is considered the "fundamental" fold from which map and filter can be derived.

map and filter are folds in disguise

Because a fold can build a new list as its accumulator, even map and filter are just folds. Seeing this is the moment fold clicks — it's the universal list-consumer.

const xs = [1, 2, 3, 4, 5]; // map, as a fold const doubled = xs.reduce((acc, x) => [...acc, x * 2], [] as number[]); // filter, as a fold const evens = xs.reduce( (acc, x) => (x % 2 === 0 ? [...acc, x] : acc), [] as number[], ); console.log("doubled:", doubled); console.log("evens:", evens);

Two folding hazards: