F2 · Functional Programming
map / filter / reduce (folds)
A fold collapses a list to a single value by threading an accumulator through it, combining one
element at a time. Enum.reduce is that fold — and it is the one list operation the
others are built from.
F2.04 ended on the observation that sum, length, reverse, map, and filter are all the same
recursion with a different combiner. This module makes the combiner the subject. Give reduce
a starting value and a function of (element, accumulator), and it walks the list
left to right, replacing the accumulator at each step. Change the combiner and the same machine computes a
sum, a product, a maximum, a count — or builds a whole new list, which is how map and filter fall out of
it.
A left fold · sum [1, 2, 3, 4]
acc = 0 · queued 1
Each step folds the next element in: acc = acc + x.
How a fold runs
A fold starts with an accumulator and visits each element in turn. At every step it applies the combiner to the current element and the accumulator, and the result becomes the new accumulator. When the list is spent, the accumulator is the answer.
Step through a sum, the simplest combiner.
- fold
- collapsing a list to a value by combining elements with an accumulator.
- reduce
- Elixir’s left fold:
Enum.reduce(list, acc, fun). - accumulator
- the value carried through the fold and returned at the end.
- combiner
- the function applied to each element and the accumulator.
reduce([3, 1, 4, 1], 0, &+/2) · the accumulator threads through
F2.04 · accumulators
The same accumulator from tail recursion — reduce is that pattern, named and reusable.
Elixir
Enum.reduce/3 is a left fold and tail-recursive — constant stack space.
A fold is one starting value plus one combiner applied down the list. Everything else about reduce is a choice of those two.
Change the combiner
The walk is fixed; the combiner and starting value are not. Swap them and the same fold computes a sum, a product, a maximum, or a count — without touching how the list is traversed.
Pick a combiner.
One skeleton, four results · over [3, 1, 4, 1]
F1.07 · operators
Sum and product were the same operator with a different combining step. So is every reduce.
Elixir
One reduce, many reductions — the combiner names which.
Reductions to a single value differ only in the combiner and the start. The traversal is the part you never rewrite.
The universal fold
The accumulator need not be a number. Let it be a list and the fold builds a list — which is exactly
what map and filter do. Map appends each transformed element; filter appends only those that pass. Both are
reduce with a list accumulator. Reduce can express map and filter; map and filter
cannot express reduce. That is why reduce is the fundamental one.
See each derived from reduce.
map and filter, built from reduce
Idea
The most general list operation is the one that can rebuild the list as it goes.
Elixir
In practice reach for Enum.map and Enum.filter for clarity — reduce when neither fits.
Reduce is the list eliminator: hand it a list accumulator and it subsumes map and filter. Knowing that, you can derive the rest.
Four deep dives
This module continues across four pages — each of the three core operations on its own terms, then the wider toolkit they all belong to. Read them in order.
What this lands
A fold is a starting value and a combiner threaded down a list. reduce is that
fold, left to right and tail-recursive, so it carries the accumulator the F2.04 way without growing the
stack. Swap the combiner and one machine yields sum, product, max, or count; give it a list accumulator and
it becomes map and filter. That is the sense in which reduce is universal — it is the operation the
others reduce to. The four deep dives above take map, filter, reduce, and the wider toolkit one at a time;
F2.06 then turns to the functions those combiners so often are: closures that capture a value from around
them.
Start with map, then filter, reduce, and advanced folds. Next module: F2.06 — Closures & partial application.