Higher-order operators (Σ, Π)

The summation and product signs are functions in disguise: each takes another function and a range and folds them into one value. The same idea, generalised, is map, filter, and reduce.

F1.01 made functions into values; a higher-order operation is one that takes a function as an argument. Mathematics has had these for centuries in Σ and Π. We start there, meet the three everyday operators that capture the recursion of F1.06 once and for all, and end on reduce — the one the others are special cases of.

Sigma and Pi Map, filter, reduce Reduce is the general one

Sigma and Pi

Written in full, Σ_i=1ⁿ f(i) means: take each i from 1 to n, apply f, and add the results. It is parameterised by the function f — that is what makes it higher-order. Π is the same with multiplication in place of addition.

Choose a function and an operator and watch the range expand and fold.

higher-order: an operation that takes a function as an argument — like Σ.
map: apply f to every element; same shape out.
filter: keep the elements a predicate accepts; fewer out.
reduce: fold every element into one value with a combining function.

Σ and Π · an operator over a function

n 4

Σ i² for i = 1..4 · 1 + 4 + 9 + 16 = 30

Algebra

Σ_i=1ⁿ f(i) applies f across a range and adds; Π multiplies.

Elixir

Enum.reduce(1..n, 0, fn i, acc -> acc + f.(i) end) — the operator, made general.

A big operator is a fold waiting to happen: a function applied across a range, then combined. Change the combine and you change the operator.

Map, filter, reduce

Three higher-order operations do most of the work over collections. map applies a function to each element and keeps the shape. filter keeps only the elements a predicate accepts, so the result is usually shorter. reduce folds everything into a single value. Same list, three different effects on its shape.

Pick an operation and see what comes out.

One list · three shapes

Enum.map(list, &(&1 * 2)) → [2, 4, 6, 8, 10, 12] · length preserved, 6 → 6

Algebra

Transform each, select some, or combine all — three ways to act on a collection.

Elixir

Enum.map/2, Enum.filter/2, Enum.reduce/3 — each takes a function.

Map preserves the shape, filter shrinks it, reduce collapses it to one. Reach for the one whose effect on the shape matches what you want.

Reduce is the general one

Reduce folds a collection into an accumulator, one element at a time, using a combining function and a starting value. Choose addition from zero and it is Σ; choose multiplication from one and it is Π; build a list and you have map or filter. The combiner and the starting value decide which operation reduce becomes.

Step through the fold and watch the accumulator.

reduce([1, 2, 3, 4]) · the accumulator

step 4 / 4

done · reduce with + from 0 = 10 · this is Σ

Algebra

A fold over a list with an operator and an identity — Σ, Π, and the rest are instances.

Elixir

Enum.reduce(list, acc0, fn x, acc -> combine end) — map and filter included.

Reduce is the single operation underneath the others: pick a combiner and a starting value and it becomes sum, product, map, or filter. It is the accumulator recursion of F1.06, named.

What this lands

A higher-order operation takes a function as an argument, and the oldest examples are Σ and Π. In code the trio is map, filter, and reduce: transform, select, combine. Reduce is the general one — the others, and the big operators, are special cases of a fold with a chosen combiner and starting value — and it is exactly the accumulator recursion of F1.06 written once. With F1.01’s first-class functions and F1.05’s collections, this closes the algebra of F1. F1.08 turns to pattern matching, and F2 makes these operators the everyday shape of functional code.

Next: F1.08 — Equations & pattern matching (planned) — solving by structure, the destructuring side of the match operator. The rest of F1 is on the chapter page.