Higher-order functions

Lesson 02 left us re-typing the same control skeletons — accumulate-while-counting, shrink-and-recombine — with only the combining step changing, and named that repetition as the pressure that demands a new abstraction. This lesson grants it. We make functions first-class values: things you can name, pass as arguments, and return as results, exactly like numbers. A function that takes or returns a function is a higher-order function. This is not syntactic convenience — it is a genuine means of abstraction that lets you name a pattern of computation, the thing lesson 02 could not name. We build it up to its sharpest payoff: a single fixedPoint machine that, fed the right function, computes square roots.

1 · Functions as arguments — naming a pattern

Three functions: sum of integers a..b, sum of their cubes, and a series for π/8. Written separately they share a skeleton and differ in exactly two spots — the term applied to each value and how to get the next value:

function sumInts(a, b)  { return a > b ? 0 : a       + sumInts(a + 1, b); }
function sumCubes(a, b) { return a > b ? 0 : a*a*a   + sumCubes(a + 1, b); }
function piSum(a, b)    { return a > b ? 0 : 1/(a*(a+2)) + piSum(a + 4, b); }

The repetition lesson 02 warned about, in the flesh. Because functions are first-class, we can pass the two varying pieces as functions and write the skeleton once. This is the higher-order function sum — itself the mathematical idea of summation, captured as code:

function sum(term, a, next, b) {        // term and next are FUNCTIONS
  return a > b ? 0 : term(a) + sum(term, next(a), next, b);
}
const id    = x => x;
const inc   = x => x + 1;
const cube  = x => x * x * x;

const sumInts2  = (a, b) => sum(id,   a, inc, b);
const sumCubes2 = (a, b) => sum(cube, a, inc, b);

We have named the pattern itself. sum is an abstraction over a whole family of functions, parameterized by behavior, not just by data. That is the leap lesson 02's means of abstraction could not make — it could name a process, but not a pattern shared across processes — and it is why first-classness is an abstraction mechanism, not syntax sugar.

2 · Generalize again — accumulate, lambda, and let-as-lambda

sum hard-wires + and a base of 0. Abstract those too and you get accumulate, of which sum and product are both special cases:

function accumulate(combiner, nullValue, term, a, next, b) {
  return a > b ? nullValue
              : combiner(term(a), accumulate(combiner, nullValue, term, next(a), next, b));
}
const sum2     = (term, a, next, b) => accumulate((x, y) => x + y, 0, term, a, next, b);
const product2 = (term, a, next, b) => accumulate((x, y) => x * y, 1, term, a, next, b);
const factA    = n => product2(id, 1, inc, n);   // factorial, for free

The anonymous functions (x, y) => x + y are lambdas — function values written inline without a declared name, used exactly where a one-off function is needed. A lambda is the thing a function declaration names; the declaration is just a lambda plus a name. The same identity explains local names: a local binding (let r = ... inside a body) is sugar for immediately applying a lambda whose parameter is that name. So "introduce a local name" and "apply an anonymous function" are the same operation — a fact lesson 09 and 10 will exploit when we model scope precisely.

3 · Functions as returned values — building functions at runtime

First-classness cuts both ways: a function can return a function. This lets us build new functions programmatically. Average damping takes any function f and returns a new function that averages f(x) with x — a transformation on functions:

const averageDamp = f => (x => (x + f(x)) / 2);   // takes a fn, RETURNS a fn

averageDamp(x => x * x)(10);   // = (10 + 100)/2 = 55

The returned arrow closes over f — it remembers the f it was built with. (Exactly how a returned function remembers its birth environment is the question the substitution model handles only by hand-waving; lesson 10's environment model answers it precisely. Note the IOU.) Damping matters because it stabilizes iterative searches that would otherwise oscillate, as we are about to see.

4 · Fixed points — a general method, and Newton generalized

A fixed point of a function f is a value x with f(x) = x. For many functions you can find one by iterating: apply f repeatedly until the value stops changing. That search is itself a higher-order function — it takes the function whose fixed point we want:

function fixedPoint(f, start) {
  const tol = 1e-7;
  function iter(guess) {
    const next = f(guess);
    return Math.abs(next - guess) < tol ? next : iter(next);
  }
  return iter(start);
}

fixedPoint(Math.cos, 1.0):
 guess     cos(guess)
 1.00000   0.54030
 0.54030   0.85755
 0.85755   0.65429
 0.65429   0.79348
   ...        ...
 0.73909   0.73909   <- converged: cos(x) = x at x = 0.73909

Newton's method (lesson 01's sqrt engine) is itself just fixed-point search of a derived function. The root of g is a fixed point of x − g(x)/g′(x). So newtonsMethod is a higher-order function that takes g, builds that derived function, and hands it to fixedPoint. We have abstracted the abstraction.

5 · sqrt as a fixed point — the payoff

√x is the value y with y = x/y — i.e. a fixed point of y ↦ x/y. Naively iterating that oscillates (it bounces between guesses and never settles), which is precisely what average damping fixes. So:

const sqrt = x => fixedPoint(averageDamp(y => x / y), 1.0);

sqrt(2);   // => 1.41421356...

Stare at that one line. Lesson 01's sqrt was a custom block with hand-written improve, isGoodEnough, and iter helpers. Here sqrt is assembled from independently reusable higher-order parts — fixedPoint (a general search), averageDamp (a general stabilizer), and a one-line lambda for the specific equation. Each part is a named pattern, testable and reusable on its own; sqrt is their composition. That is the entire promise of higher-order functions cashed out: programs built by snapping together named methods, not by re-coding skeletons.

Common mistakes / failure modes

Checkpoint exercise

const compose = (f, g) => (x => f(g(x)));

Where this points next

We can now abstract over behavior: a control pattern is a value with a name, and programs are composed from reusable methods rather than hand-coded skeletons. But notice what every function in this entire part has operated on — numbers. sum, fixedPoint, sqrt: all push single numeric values through. Real programs manipulate compound things — a rational number is a numerator and a denominator, a point is an x and a y, a record is many fields glued together — and they need to glue those parts into a unit, pass it around as one object, and pull the parts back out, all without callers knowing how the gluing is done. Higher-order functions gave us abstraction over procedures; they give us nothing for building and hiding compound data. That gap — programs need to manipulate compound data behind a boundary, just as sqrt hid its process behind a contract — is the pressure that forces lesson 04: data abstraction, where a data type becomes a contract between constructors and selectors separated by an abstraction barrier.

Interview prompts

• What makes a function "higher-order," and why is first-classness an abstraction mechanism rather than syntax sugar? (§1 — it takes or returns functions; passing the varying piece as a function lets you name a pattern across functions (e.g. sum), an abstraction that procedure-naming alone cannot express.)
• Show how sum and product are both accumulate. (§2 — accumulate takes a combiner and a null value; sum uses (+, 0), product uses (*, 1); both reuse the same enumerate-and-combine skeleton.)
• What is a lambda, and how does it relate to local names? (§2 — a lambda is an unnamed function value; a function declaration is a lambda plus a name, and a local binding let x = e in body is just ((x) => body)(e) — an applied lambda.)
• Give an example of a function that returns a function and explain what it captures. (§3 — averageDamp(f) returns x => (x + f(x))/2, closing over f; how it "remembers" f is precisely defined later by the environment model (lesson 10).)
• What is a fixed point, and how is Newton's method a special case? (§4 — a value with f(x)=x, found by iterating f until it stops changing; Newton's method finds a root of g as the fixed point of x − g(x)/g′(x), built and handed to fixedPoint.)
• Express sqrt as a fixed point and explain why average damping is required. (§5 — √x is a fixed point of y ↦ x/y, but iterating that oscillates; averageDamp averages each step with the prior guess so it converges: fixedPoint(averageDamp(y => x/y), 1.0).)
• Why do higher-order functions not solve the problem of compound data? (§ Where next — they abstract over behavior but operate on single (numeric) values; gluing parts into a unit and hiding the representation behind a contract is a separate need that forces data abstraction (lesson 04).)