Seeing Structure First
A reflection on eleven explorations in generic programming, and how algorithms arise from algebraic structure.
1
of 19
← All Series
Algorithms Arise from Algebraic Structure
A pedagogical series exploring generic programming through the lens of abstract algebra
Algorithms Arise from Algebraic Structure
This is a collection of nineteen posts and one interactive explorer about a single idea: the algebraic structure of a type determines which algorithms apply to it.
The idea is Stepanov’s. I’ve been working through it for seven years, and these posts are the record. Each one takes an algebraic structure (monoid, ring, lattice, free algebra), implements it in ~200 lines of C++, and shows what algorithm falls out.
The implementations are pedagogical. They teach principles, not production patterns. The code reads like a textbook that happens to compile.
The Principle
When you say “this type is a monoid,” you’re transmitting an enormous amount of information in a few bits. A monoid guarantees associativity, which is infinitely many facts about every triple of elements. It guarantees an identity, which is infinitely many facts about every element’s interaction with it.
Algorithms exploit this compressed information. power() doesn’t need to be told that $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for your particular type. It knows because you declared the structure. Each law you can assume is exponentially more constraint you don’t have to check.
This is why the same twenty lines of code compute integer powers, Fibonacci numbers (via matrices), compound interest (via affine transforms), shortest paths (via the tropical semiring), and string repetition. They share monoid structure. The algorithm follows.
The Hierarchy
Each algebraic structure adds laws, and each law unlocks algorithms:
| Structure | What it adds | What it enables |
|---|---|---|
| Semigroup | Associativity | Parallel reduction |
| Monoid | + identity | Power by squaring, O(log n) |
| Group | + inverses | Division, negative powers |
| Semiring | Two monoids + distributivity | Graph algorithms via matrix power |
| Ring | + subtraction | Polynomial arithmetic |
| Field | + division | Linear algebra, Gaussian elimination |
| Euclidean domain | + division with remainder | GCD (same algorithm for integers and polynomials) |
| Ordered field | + total order | Numerical integration |
| Lattice | Meet and join | Fixed-point iteration, abstract interpretation |
Minimal requirements maximize applicability. The peasant algorithm doesn’t require commutativity, so quaternions and matrices work. Integration doesn’t require std::floating_point, so dual numbers and rationals work. Every unnecessary requirement excludes types that could participate.
Beyond Stepanov: Structure of the Maps
Stepanov’s original insight covers the structures and their algorithms. But there’s a second layer I’ve been exploring in the later posts: the maps between structures tell you just as much as the structures themselves.
A homomorphism is a function that preserves structure: $f(a \oplus b) = f(a) \oplus f(b)$. This isn’t an abstract definition. It’s a concrete property of functions you already use:
length(s1 + s2) = length(s1) + length(s2)(length preserves concatenation)log(a * b) = log(a) + log(b)(log converts multiplication to addition)sum(xs ++ ys) = sum(xs) + sum(ys)(sum preserves list concatenation)
These aren’t coincidences. They’re homomorphisms. And the reason fold works on any monoid is that fold is the universal homomorphism from the free monoid (lists) to any target monoid. That’s a theorem, not a design pattern.
This connects to parallelism. If $f$ is a homomorphism, you can split the input, apply $f$ to each piece, and combine the results. The homomorphism property guarantees correctness. Parallelism isn’t a feature you add. It’s a consequence of algebraic structure.
What “Free” Means
Lists are the free monoid: the most general monoid on a set of generators. No equations hold except those the axioms force. $[a, b]$ is never equal to $[b, a]$ (no commutativity). $[a, a]$ is never equal to $[a]$ (no idempotency). The structure is as general as possible.
The universal property says: for any function $f: T \to M$ where $M$ is a monoid, there exists a unique homomorphism from the free monoid on $T$ to $M$. That homomorphism is fold. The universal property says fold is the only correct way to interpret a list in a monoid.
Polynomials are the free commutative ring. This is why the polynomial post and the free algebra post are connected: they’re both about free algebraic structures, just at different levels of the hierarchy.
Six Principles
After nineteen posts, I can state the principles that recur:
Structure determines algorithms. Recognize the structure, the algorithm follows. This is Stepanov’s original insight.
Laws determine complexity. Associativity gives O(log n). The Euclidean property gives GCD. Lattice monotonicity gives convergent iteration. Each law buys a specific computational capability.
Homomorphisms explain composition. When components preserve structure, they compose correctly. fold, polynomial evaluation, and parallel reduction are all homomorphisms. This is why they work.
Free algebras explain universality. Lists and polynomials appear everywhere in programming because they’re the most general instances of their algebraic kind. The universal property says why fold is the right operation on lists.
Minimal requirements maximize applicability. Don’t require commutativity if you don’t use it. Don’t require
std::floating_pointifordered_fieldsuffices. Each unnecessary constraint excludes types that could participate.Structure is compressed information. Declaring “this is a monoid” transmits infinitely many facts. Algorithms exploit this compression. Property-based tests verify it.
The Posts
Foundations
- One Algorithm, Infinite Powers: The Russian peasant algorithm on fifteen monoids
- Modular Arithmetic as Rings: Finite rings and fields, Fermat’s theorem
- Is It Prime?: Error bounds from group theory
- Exact Rational Arithmetic: Canonical form as theorem
- Polynomial Arithmetic: Euclidean domains, same GCD for integers and polynomials
Applied Mathematics
- Pedagogical Linear Algebra: Matrix concept, LU decomposition
- Forward-Mode Autodiff: Dual numbers, derivatives from algebra
- Numerical Differentiation: Truncation vs. round-off
- Reverse-Mode Autodiff: Computational graphs, chain rule
- Numerical Quadrature: Generic integration, Leibniz rule via composition
Programming Patterns
- Runtime Polymorphism: Sean Parent’s technique on algebraic structures
- Streaming Statistics: Accumulators as monoids, product monoid composition
- Graph Algorithms: One matrix power, six graph problems via semirings
- Fixed Points: Lattices, Tarski’s theorem, abstract interpretation
Algebraic Foundations
- The Maps Between Structures: Homomorphisms, fold as universal map
- Why Lists and Polynomials Are Universal: Free algebras, universal property
Reflections
- Differentiation: Three Ways: Forward AD, reverse AD, finite differences compared
- Seeing Structure First: The meta-pattern across eleven posts
- Duality: Mathematical opposites and what they reveal
Interactive Explorer
The explorer is a visual map of the algebraic hierarchy and how each post connects to it. Click a structure to see its laws, concept definition, and associated algorithms. Click a post to see its core insight and code.
Further Reading
- Stepanov & Rose, From Mathematics to Generic Programming
- Stepanov & McJones, Elements of Programming
- Sean Parent, “Inheritance Is The Base Class of Evil” (GoingNative 2013)
- Chan, Golub & LeVeque, “Updating Formulae and a Pairwise Algorithm for Computing Sample Variances”
- Cousot & Cousot, “Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs”
Posts in this Series
Showing 19 of 19 posts
1
of 19
One Algorithm, Infinite Powers
The Russian peasant algorithm computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.
2
of 19
Modular Arithmetic as Rings
Integers modulo N form a ring, an algebraic structure that determines which algorithms apply. Understanding this structure unlocks algorithms from cryptography to competitive programming.
3
of 19
Is It Prime?
The Miller-Rabin primality test demonstrates how probabilistic algorithms achieve arbitrary certainty, trading absolute truth for practical efficiency.
4
of 19
Exact Rational Arithmetic
Rational numbers give exact arithmetic where floating-point fails. The implementation connects GCD, the Stern-Brocot tree, and the algebraic structure of fields.
5
of 19
Polynomials as Euclidean Domains
The same GCD algorithm works for integers and polynomials because both are Euclidean domains. One structure, many types, same algorithms.
6
of 19
Teaching Linear Algebra with C++20 Concepts
elementa is a linear algebra library built to teach. Every design decision prioritizes clarity over cleverness. Code that reads like a textbook and compiles.
7
of 19
Forward-Mode Automatic Differentiation
Dual numbers extend our number system with an infinitesimal epsilon where epsilon^2 = 0. Evaluating f(x + epsilon) yields f(x) + epsilon * f'(x)—the derivative emerges automatically from the algebra.
8
of 19
Numerical Differentiation
Choosing step size h for finite differences: small enough for a good approximation, not so small that floating-point errors eat your lunch.
9
of 19
Reverse-Mode Automatic Differentiation
Reverse-mode automatic differentiation is just the chain rule applied systematically. I built one in C++20 to understand what PyTorch and JAX are actually doing.
10
of 19
Numerical Integration with Generic Concepts
Numerical integration meets generic programming. By requiring only ordered field operations, the quadrature routines work with dual numbers, giving you differentiation under the integral for free.
11
of 19
Runtime Polymorphism Without Inheritance
Sean Parent's type erasure gives you value-semantic polymorphism without inheritance. Combined with Stepanov's algebraic thinking, you can type-erase entire algebraic structures.
12
of 19
Differentiation: Three Ways
Three approaches to computing derivatives, forward-mode AD, reverse-mode AD, and finite differences, each with different trade-offs for numerical computing and machine learning.
13
of 19
Duality: The Hidden Structure of Opposites
Many structures come in pairs: forward/reverse AD, push/pull iteration, encode/decode. Recognizing duality lets you transfer theorems and insights between domains.
14
of 19
Streaming Statistics, One Monoid at a Time
Online accumulators are monoids. Default construction is the identity, combination via += is the binary operation, and parallel composition gives the product monoid, computing arbitrary statistics in a single pass.
15
of 19
Semirings: One Algorithm, Six Graph Problems
A semiring has two monoidal operations linked by distributivity. Matrix multiplication over different semirings gives shortest paths, longest paths, widest paths, reachability, and path counting, all from the same code.
16
of 19
Lattices: Fixed Points and Iteration
A lattice has two operations, meet and join, satisfying absorption laws. Tarski's theorem gives a generic fixed-point algorithm. Lattice structure determines the iteration, just as monoid structure determines power-by-squaring.
17
of 19
Homomorphisms: The Maps Between Structures
A homomorphism preserves structure. fold is the universal homomorphism from the free monoid. This is the algebraic reason that fold, evaluation, and parallelism work.
18
of 19
Free Algebras: Why Lists and Polynomials Are Universal
The free monoid on a set is the type of lists over that set. The universal property says fold is the unique homomorphism from lists to any monoid. This explains why lists, multisets, and polynomials appear everywhere.