Applied Higher Order Functions
A functional architecture of optimisation, decision making and validation.
Operations research is usually taught as hundreds of unrelated recipes. I wrote this book to show that most of it is a small set of higher-order-function patterns composed in different orders. The code is Clojure throughout.
By Jiri Knesl, founder of Flexiana
- algorithms catalogued
- about 480
- patterns underneath them all
- 10
- code listings, each parse-checked
- 167
- library dependencies (orhof)
- 0
- pages
- 347
Why the book is so long
Gradient descent, conjugate gradient and Adam are one descent
function with different parts plugged in. One example like that does not convince anyone,
so I showed the same thing for every algorithm in the book, across three fields
that are usually taught in separate courses.
The catalogue at the back lists each algorithm with its patterns, so you can check it yourself.
We also use it at Flexiana. When we model a client's decision, senior people can pass work to each other without explaining the basics again.
What is inside
Each chapter builds its algorithms in Clojure and ends with exercises. A delivery robot example runs through seven chapters, and short “Making Math Approachable” sections explain the maths as it comes up.
- I
The Foundation of Higher-Order Functions
- 1
The Crisis of Representation
Why optimisation code turns into tangled loops, and why the algorithms underneath are the same. Worked through on a thermostat.
- 2
The Native Vocabulary of Algorithms
iterate, reduce, comp and partial: the four functions everything after is built from. Applied to online fraud detection.
- 3
How to Design a Higher-Order Function
From a formula to a function signature: anatomy, naming and anti-patterns. Applied to React hooks and MapReduce.
- 1
- II
The Algorithmic Toolkit
- 4
The Population Pipeline
Genetic algorithms, particle swarms, differential evolution and the cross-entropy method as one pipeline. Applied to evolving antenna designs.
- 5
The Descent Framework
Gradient descent, Newton, momentum, Adam and Lion as one descent function with swappable parts. Applied to training a neural network.
- 6
The Calculus of Constraints
Penalties, augmented Lagrangians, barrier methods, simplex and multi-objective optimisation as wrappers around a problem. Applied to supply-chain logistics.
- 4
- III
HOFs for Decision Making
- 7
The Bellman Operator
Markov decision processes, with value iteration and policy iteration as iterate applied to functions. Applied to routing internet traffic.
- 8
Online Learning and the Fold Pattern
Q-learning, SARSA, Bayesian updating and particle filters as folds over a stream. Applied to A/B testing.
- 9
Monte Carlo Tree Search
Minimax, then MCTS assembled from four strategy functions, with parallel rollouts. Applied to finding bugs in compilers.
- 7
- IV
HOFs for Validation
- 10
Temporal Logic as Function Combinators
always, eventually and until as functions that return a safety margin. Applied to autonomous vehicle testing.
- 11
Falsification as Optimization
Finding the input that breaks a system by optimising against its specification. Applied to airborne collision avoidance.
- 12
Reachability and Sensitivity
Propagating sets, zonotopes, and sensitivity by Shapley value. Applied to drug dosage safety.
- 10
- V
Synthesis and Architecture
- 13
Practical HOF Idioms
Memoisation, transducers, reducers, protocols and decorators. Applied to recommender systems.
- 14
Cross-Domain Composition
Pipelines, nesting and feedback loops across all three domains, with AlphaGo Zero taken apart as the worked example.
- 15
The Algorithm Taxonomy
Optimisation, decision, validation and machine-learning algorithms annotated with their patterns, and how to read one you have not met.
- 16
Practical HOF Idioms and Library Design
Naming, signatures, testing, performance and library architecture: how orhof is built.
- 13
Appendices
- A
Clojure Primer for the Mathematically Inclined
- B
Complete Library API Reference
- C
Quick Reference: Algorithm–Pattern Mapping
;; 1847: Gradient descent (Cauchy)
(descent {:direction-fn (fn [s] (mapv - (:grad s)))
:step-fn (fn [_ _] 0.001)
:f f :x0 x0})
;; 1847: Steepest descent (Cauchy + line search)
(descent {:direction-fn (fn [s] (mapv - (:grad s)))
:step-fn (backtracking-line-search f ...)
:f f :x0 x0})
;; 1669: Newton's method (Newton + line search)
(descent {:direction-fn (fn [s] (mapv - (solve-linear
(hess-f (:x s))
(:grad s))))
:step-fn (backtracking-line-search f ...)
:f f :x0 x0})Gradient descent, steepest descent and Newton's method are each one call to the same descent function. Only the two strategy functions change.
The library and the prover behind it
Companion library
orhof
The Clojure library that builds the book's algorithms from higher-order-function patterns. Appendix B is its reference, and every listing in the book is written against it.
Theorem prover
Rainbow
Our theorem prover checks the book's structural claims, one algorithm at a time.
The hardback
Order the hardback
€75 a copy, including VAT, plus shipping. Orders inside the EU are posted from Spain, so there is nothing to pay on delivery. Orders from everywhere else are posted from Gibraltar.
We reply by email with the shipping cost and an invoice from Flexiana s.r.o., and post the book once it is paid.
Apply the book to your own decision
Tell me about a decision in your company and its constraints. Ivo or I will look at it.