The higher-order-function architecture of operations research

Operations research reaches its students as a catalogue: a chapter on gradient methods, a separate chapter on dynamic programming, another on model checking, each with its own notation and its own apparatus. The catalogue is honest about what the algorithms do and quiet about what they share. This paper, the organising thesis of the book Applied Higher Order Functions, argues that three of the largest branches of the field share one small vocabulary of higher-order functions, and that writing them that way makes the shared structure impossible to miss.

One descent, many methods

Consider first-order optimisation. Gradient descent, conjugate gradient and Adam are taught as three methods; they are better read as one skeleton with different arguments. A generic descent framework takes a way to compute a direction and a way to update state, and iterates. Supply the plain negative gradient and you have gradient descent. Supply a conjugate direction rule and you have conjugate gradient; supply Adam’s first- and second-moment update and you have Adam. The control flow is written once. What differs between the methods is not the loop but the two functions handed to it, and that is exactly where the real mathematical content lives.

Bellman as a function transformer

Sequential decision-making under uncertainty gets the same treatment. The Bellman operator is normally written as an equation over value functions. Read it instead as a function transformer: given a Markov decision process, it returns a map V → V' from one value function to an improved one. Its type is mdp → (V → V'). Value iteration is then nothing more than applying that transformer repeatedly until the value function stops moving, and policy iteration is the same transformer used inside a different outer loop. The MDP is data. The operator is a higher-order function over value functions; the algorithms are compositions of the two. There is no loss, and the relationship between the methods becomes structural rather than incidental.

Validation as optimisation

The third branch is the surprising one. Temporal-logic operators (always, eventually, until) are usually presented as Boolean checks over a trace. Give them continuous robustness semantics instead, so that each operator returns not true/false but a real-valued margin of satisfaction, and each becomes a higher-order function that folds a scoring rule over a trace. The consequence is direct: falsification of a specification turns into an optimisation problem. Finding a counterexample to “the system is always safe” becomes minimising the robustness score, and the very same descent framework from the first section is the tool that does it. Validation and optimisation, kept in separate chapters everywhere else, are revealed as the same activity seen from two sides.

Evidence and its boundary

The thesis is executable, not just asserted. The book catalogues roughly 480 algorithms on this basis, is print-ready under CC BY-SA 4.0, and every listing is written against the orhof library, so a reader can re-run each composition and confirm the identity for themselves. The same catalogue is the proving curriculum for Rainbow, which machine-checks a growing subset of these algorithms against a small trusted kernel, the compositions are not only runnable but, increasingly, verifiable.

The boundary is where the honesty is. This is a structural and pedagogical result, not a performance one. The higher-order-function readings are re-expressions of established algorithms; their payoff is a smaller conceptual surface, genuine reuse, and code that shows its own structure, not faster wall-clock time on large instances, and not new mathematics. The reference implementations are written to be read. Read that way, a field that looked like a long list of separate inventions looks instead like a short list of functions, composed.