The idea: functions that take functions
A higher-order function takes another function as an argument (or returns one). The three most used ones work on lists. map(f) calls f on every item. filter(p) keeps the items where the test p is true. reduce(g, init) folds the list into one value. Put together, they form a pipeline: each stage takes a list and returns a new one.
On the canvas the data panel shows each list as a row of boxes. A yellow box is the function being called: it slides under the item it works on. The code panel highlights the line that runs, and the Variables panel shows what each name holds.
map, filter and reduce
| Function | Calls | Returns | On the default list |
|---|---|---|---|
xs.map(f) | f once per item | a new list, same length | [6, 16, 10, 24, 14, 20] |
ys.filter(p) | p once per item | a new list, items where p is true | [16, 24, 14, 20] |
zs.reduce(g, 0) | g once per item | one value | 74 |
None of the three changes its input: after Demo: map doubles every item, xs is still [3, 8, 5, 12, 7, 10]. In Python the same pipeline is map(f, xs), filter(p, ys) and functools.reduce(g, zs, 0), or a comprehension such as sum(y for y in (x * 2 for x in xs) if y > 10). In Java it is stream().map(f).filter(p).reduce(0, Integer::sum).
The accumulator
reduce keeps a running value, the accumulator. It starts at the start value. For each item it calls g(acc, x), and the result becomes the accumulator for the next item. With acc + x the accumulator goes 0 → 16 → 40 → 54 → 74 (Demo: reduce sums with an accumulator). reduce is also called a fold (a left fold, because it starts at the left end).
The combining function decides what reduce computes. With Math.max(acc, x) it finds the largest item, with acc + 1 it counts. Demo: squares, even, max maps [1, 2, 3, 4, 5, 6] to the squares [1, 4, 9, 16, 25, 36], keeps the even ones [4, 16, 36] and folds them with max: 36. On an empty list, reduce returns the start value without calling g.
The same task as a loop
A for loop gets the same answer by changing variables in place. let total = 0, then for each x it overwrites y and maybe total (Demo: the same task as a loop). On the default list it writes x 6 times, y 6 times and total 5 times: 17 writes for one answer.
The loop is not wrong, and it is often faster. But to know what total holds at some moment you have to replay the loop up to that point. In the pipeline, every name has one value for its whole life, so you can read each stage on its own, test it on its own and reorder or reuse it.
Pure functions and side effects
A function is pure when (1) its result depends only on its arguments, and (2) it has no side effects: it does not change a global, write a file, print or change an argument. double(x) = x * 2 is pure: double(10) is 20 every time. bump(x) adds 1 to a global calls and returns x + calls, so bump(10) gives 11 and then 12 (Demo: pure vs hidden side effect). Nothing in the call bump(10) tells you that.
The functions you pass to map, filter and reduce should be pure. Then the result does not depend on the order of the calls, so a library may run them in parallel, as MapReduce does across many machines.
Referential transparency
An expression is referentially transparent if you can replace it by its value without changing the program. Calls to a pure function are: double(5) + double(5) becomes 10 + 10, and computing v = double(5) once and writing v + v also gives 20.
next() adds 1 to a global n and returns it. Starting from n = 0, next() + next() is 1 + 2 = 3, but v = next(); v + v is 1 + 1 = 2 (Demo: substitution (referential transparency)). This is why compilers can cache or remove repeated calls of pure functions (as memoization does), and why they must not do it for impure ones. Pure functions also suit data that never changes, such as persistent trees.
A note on lazy pipelines
On this page each stage builds its whole list before the next one starts. Python's map and filter, Java streams and Haskell lists are lazy instead: nothing runs until the end of the pipeline asks for a value, and then each item goes through all stages one at a time, with no lists in between. Laziness only gives the same answer when the functions are pure.
See also tail calls, the recursive way to write the same loop with an accumulator, and Java lambdas and invokedynamic, how the JVM turns x -> x * 2 into an object.
See also closures and currying, which shows how a function returned from another function keeps its variables, and how add(2)(3) and partial application work.
What the page leaves out
The page uses JavaScript arrays of at most 6 small integers and builds each list fully before the next stage. It leaves out closures and currying, functions that return functions, right folds (reduceRight, foldr), laziness and infinite lists, how a side effect is kept apart in a pure language (monads in Haskell), and parallel reduce, which needs an associative g.