Some types arrive with their operations already specified — by mathematics. If a type is a number, a set, or a sequence, math has written the complete API for us; the work is to implement it, and to implement it efficiently.

Contains an ode to Alexander Stepanov. The links to his books are affiliate links: if you buy one, I may earn a commission at no extra cost to you.

The first post argued for completeness: find the complete shape of an API first, then cut. It named several places that shape comes from, and this post takes the cleanest one. When a type is grounded in mathematics, the math already prescribes its operations, and we only have to recognize them. Alexander Stepanov built the C++ Standard Template Library (STL) on exactly this idea, and the lasting lesson is what he chose to implement, and why.

When the domain is math, the API is prescribed

The structure a type satisfies (a monoid, a semiring, a ring, a field) comes with a known set of operations attached, and that set is the API. Stepanov and Daniel Rose make this the whole thesis of From Mathematics to Generic Programming: generic operations derive from the algebraic structure underneath. To use its lesson we need only the one move it teaches, which is to let the math decide what belongs.

What we inherit is more than the names. Math, and computer science with it, has already worked out the correctness of those operations and what they cost. We implement instead of discovering, and we get fewer surprises later.

The structures are few, and they come up often. Each one is a type with a few operations, plus laws the operations must obey. The operations are the API, and the laws are its contract. Each structure’s defining operations are binary: they take two values of the type and return a value of the same type. The laws are the other requirements, listed with each structure below. Any function that meets them qualifies, so min can play addition just like +. Each structure keeps everything the previous one had and adds to it.

Monoid

A monoid has one operation, op, and one special value, its identity e. Applied to the identity and any value, the operation returns that value unchanged. The operation is associative: grouping does not change the result.

op(op(a, b), c) === op(a, op(b, c)); // associative
op(a, e) === a; // identity on the right
op(e, a) === a; // and on the left

Familiar monoids:

x + 0 === x;
x * 1 === x;
str + "" === str;
Math.max(x, -Infinity) === x;
(flag && true) === flag;

The order of operands may matter: "a" + "b" differs from "b" + "a", and strings are still a monoid. A function that takes and returns strings can still fail. This one has no identity, and grouping changes its result:

const op = (x, y) => "abc" + y + "-" + x;
op(op("1", "2"), "3"); // "abc3-abc2-1"
op("1", op("2", "3")); // "abcabc3-2-1"

Semiring

A semiring has two such operations, addition and multiplication, each with its identity: add with zero, and mul with one. Both are monoids, and addition is also commutative. Two more laws tie them together: multiplication distributes over addition, and multiplying by zero gives zero.

add(a, b) === add(b, a);
mul(a, add(b, c)) === add(mul(a, b), mul(a, c));
mul(add(a, b), c) === add(mul(a, c), mul(b, c));
mul(a, zero) === zero;
mul(zero, a) === zero;

Natural numbers with + and * are the model, but add and mul are roles, and other functions can fill them. Booleans form a semiring with || as addition and && as multiplication, so zero is false and one is true. Distances form one with min as addition and + as multiplication: zero is Infinity, one is 0, and distributivity reads a + min(b, c) === min(a + b, a + c). Sets form one with union and intersection: zero is the empty set, and one is the universe, all the values in play.

The semiring deserves the most attention. It asks for no inverses, and many types in computing lack them: nothing undoes a min, and a count cannot go below zero. That gives the semiring many instances, and one algorithm serves all of them. A matrix multiply needs nothing beyond a semiring, so we write it once and pass the semiring in:

const arithmetic = {
  zero: 0, one: 1,
  add: (a, b) => a + b,
  mul: (a, b) => a * b
};
const shortest = {
  zero: Infinity, one: 0,
  add: Math.min,
  mul: (a, b) => a + b
};
const reachable = {
  zero: false, one: true,
  add: (a, b) => a || b,
  mul: (a, b) => a && b
};

const multiply = (s, A, B) => {
  const C = [];
  for (let i = 0; i < A.length; ++i) {
    C[i] = [];
    for (let j = 0; j < B[0].length; ++j) {
      let sum = s.zero;
      for (let k = 0; k < B.length; ++k) {
        sum = s.add(sum, s.mul(A[i][k], B[k][j]));
      }
      C[i][j] = sum;
    }
  }
  return C;
};

It is the textbook loop: each cell of the result is a sum of products over a row of A and a column of B. The only change is that the sum starts from s.zero and uses s.add and s.mul in place of 0, +, and *. With arithmetic it is the ordinary matrix product.

With shortest it finds shortest routes. Take three places, A, B, and C, numbered 0, 1, and 2. The matrix roads holds the direct distances between them: roads[0][1] is the distance from A to B. Infinity means there is no direct road, and 0 on the diagonal is the distance from a place to itself:

const I = Infinity;
const roads = [
  [0, 5, 9], // from A: to B is 5, to C is 9
  [I, 0, 2], // from B: to C is 2
  [I, I, 0]  // from C: no roads out
];
const twoRoads = multiply(shortest, roads, roads);
twoRoads[0][2]; // 7: from A to C through B

Why multiply roads by itself? Under shortest, the loop computes each cell as the smallest roads[i][k] + roads[k][j] over every place k: the shortest way from i to j with one stop k on the way. Staying put costs 0, so the direct road is among the candidates. From A to C the direct road is 9, and the route through B is 5 + 2 = 7, so twoRoads[0][2] is 7. The product holds the shortest distances over at most two roads. Multiplying by roads again allows three, and so on.

With reachable, and true for each direct road and on the diagonal, the same call tells which places can be reached from which over at most two roads. Matrices, polynomials, linear algebra and tensors are built over these structures and inherit their operations.

Ring

A ring adds one law to a semiring: every value has a negative, which adds up with it to zero. That gives negate, and with it subtraction:

add(a, negate(a)) === zero;
sub(a, b) === add(a, negate(b));

Integers form a ring. Natural numbers lack negatives: 3 - 5 falls outside them. Polynomials form a ring, and so do square matrices of one size, n by n: adding, subtracting, or multiplying two of them gives another n by n matrix. Two 2 by 3 matrices add and subtract, but they have no product, so rectangular matrices fall short of a ring. Matrices also show that multiplication can depend on order: A * B and B * A usually differ.

Field

A field adds two laws to a ring: multiplication is commutative, and every value except zero has an inverse, which multiplies with it to one. That gives inverse, the counterpart of negate under multiplication, and with it division.

mul(a, inverse(a)) === one; // a !== zero
div(a, b) === mul(a, inverse(b)); // b !== zero
mul(a, b) === mul(b, a);

Rationals, reals, and complex numbers are fields. Integers fall short, since 1 / 2 is a fraction, and so do matrices, many of which have no inverse. Integers modulo a prime form a field: modulo 7, 3 * 5 % 7 === 1, so 5 is the inverse of 3. The smallest field has two values: booleans, with xor as addition and && as multiplication. Every field leaves division by zero undefined, so a numeric API has to decide what 1 / 0 returns.

In any language

None of it needs a language feature. A monoid is a contract, an associative operation plus its identity, and any language can honour it:

• GraphBLAS, a C API, makes monoids and semirings first-class objects: one matrix multiply, with the semiring chosen per call, such as GrB_MIN_PLUS_SEMIRING_FP64 for shortest paths.
• Java’s Stream.reduce(identity, accumulator) requires identity to be an identity for the accumulator: a monoid stated in the documentation.
• JavaScript’s Math.max() with no arguments returns -Infinity, the identity of max. [].reduce((a, b) => a + b) throws on an empty array, while [].reduce((a, b) => a + b, 0) returns 0: without an identity there is nothing to return.

One caveat: floating-point addition is not associative, so number obeys these laws only approximately. We still design its API as if it did.

Numbers: one operation leads to the next

Take the most familiar mathematical type, a number. What does a complete numeric API owe its callers? We could list the operations, but math gives us more than a list: it gives a direction.

Addition, for sure. Having addition, we need its complement, subtraction, and with subtraction comes negation. Multiplication, yes, and then division. Division raises a question a list would miss: what is 1 / 0? So we probably need Infinity, -Infinity, and NaN. Numbers are ordered, so comparisons come next, and min, max, abs, floor, and round build on them. Domain functions such as sin, exp, and sqrt are a judgment call, but they are well studied, so if we decide to add sin() we know what comes with it: the rest of trigonometry, since practically every other trigonometric function can be defined from it (cos(x) is sin(x + PI / 2)). With exp() comes its inverse, log(), and the related pow(), and sqrt() is a frequent case of pow().

Once we implement one operation, we know it has a complement, possibly more. Inverses are common complements: subtraction undoes addition, asin() undoes sin(), and sqrt() undoes x ** 2, the last two within a limited range.

The chain also tells us where to stop. The set is the operations the domain actually uses, a small part of what mathematics can prove about numbers. Completeness here is practical completeness: cover what callers use, roughly in proportion to how often they use it, and stop where the math stops being useful to them.

Strings are the other familiar case. A string is a linear container of characters, one we use often, and its operations follow: concatenation with the empty string as its identity, then splitting, substrings, search, and eventually regular expressions.

Not only for heavy math

When I say that math can guide API design, some developers conclude that it is for people who build linear algebra libraries or coordinate systems, and not for them. In reality it applies much more widely.

Take a record with a balance. A balance here is any number we keep track of: an account, experience points in a game, whole or fractional. We can expose it as a plain value, or cover it with a getter and a setter. It has one invariant: a balance cannot be negative, and the setter enforces it.

class Account {
  #balance = 0;
  get balance() {
    return this.#balance;
  }
  set balance(value) {
    if (value < 0) {
      throw new RangeError('balance cannot be negative');
    }
    this.#balance = value;
  }
}

// at every call site:
account.balance -= amount;

The setter can put the balance into any valid state, so this shape is complete. The common operations are adding and removing, and we want them logged. The getter and the setter can express both, but three problems show up at once:

• Logging. We can log at every place that updates the balance, or in one place with one piece of code. I prefer the latter.
• The error message. When the amount is bigger than the balance, the setter catches it with a generic “balance cannot be negative”. A check before the update can say what happened: an attempt to withdraw 12 from a balance of 10.
• Atomicity. With multiple threads (not possible with plain JavaScript objects, but common in many other popular languages), the balance can change between the getter’s read and the setter’s write. Each update has to be atomic.

So we probably add two methods, which in JavaScript become something like deposit() and withdraw():

class Account {
  #balance = 0;
  get balance() {
    return this.#balance;
  }
  deposit(amount) {
    // log it, then update atomically
    this.#balance += amount;
  }
  withdraw(amount) {
    if (amount > this.#balance) {
      throw new RangeError(
        `withdraw ${amount}: the balance is ${this.#balance}`
      );
    }
    // log it, then update atomically
    this.#balance -= amount;
  }
}

The split also pays in speed. With amounts guaranteed positive, deposit() cannot make the balance negative, so it skips the check that the setter ran on every update and that withdraw() still needs. When both operations are frequent, that alone is a reason to split them intentionally.

Surely we don’t need *, /, and trigonometry? Well… Interest calculated daily on the end-of-day balance can be as simple as balance *= 1 + dailyRate. The atomicity problem is back, and if several places do it, each in its own way, correctness is hard to ensure. It belongs in the API too.

What about a balance that never goes down, such as experience points in a game without decay? On the surface we need neither a setter nor -. In reality an increase can be made in error: a bug in our code, a human operator’s mistake, hackers, an exploit. Without a way down, we fix such problems with rollbacks, which are hard when we want to keep the valuable data written since the last backup, or by modifying the database directly. I have been there: it takes custom code and manual intervention, and so it is error-prone. Some games also decay experience points to penalize infrequent players: earning is xp *= 1 + growthRate, and decay is xp *= 1 - decayRate, the same * as the interest.

So even a balance that we thought only goes up needs the complete set of operations, plus the common ones, in the interface we build. Every valid state has to be reachable from every other, one way or another.

It takes some practice to see a structure when one operand is implied. deposit() takes one argument, yet it is addition with the balance as the other operand, and the monoid of numbers carries over: 0 is the identity, and associativity takes the form of two deposits that equal one.

account.deposit(0); // the balance is unchanged
account.deposit(x);
account.deposit(y); // same balance as deposit(x + y)

Math calls this an action: the monoid acts on the balance. Nothing in the class enforces these laws, and they hold anyway. They are what lets us batch deposits into one update, or compact a log of them into one entry. Interest acts the same way through *: thirty days in a row with no other changes equal one multiplication by (1 + dailyRate) ** 30. withdraw() shows where the laws stop. From a balance of 10, withdrawing 15 and then depositing 10 throws at the first step, while the other order succeeds. The laws hold while every step keeps the balance valid, and when a step would break it, the caller gets the error message from earlier.

Containers: add, remove, iterate, and the hard ones

Containers are the other classic case, and the one Stepanov is most associated with. They have a lot in common, and they rarely care about their items: at most they know a key to sort by. The STL builds some containers from others: its stack is an adaptor over a sequence (a vector, a deque, or a list) that exposes only what a stack needs.

What does a stack need? push() and pop() change it, and they look like the whole API. Yet without isEmpty the API is incomplete: a caller cannot tell when pop() is safe, or when to stop popping. So a stack needs three operations, or a pop() that throws on an empty stack. Another frequent and useful inspector is top: a stack’s top is special, the only item it lets us see. Both top and pop() come with a precondition: the stack is not empty. The laws tie the four together:

new Stack().isEmpty; // true
stack.push(x);
stack.isEmpty; // false
stack.top; // x
stack.pop(); // x, and the stack is as it was before push(x)
// top and pop() require !stack.isEmpty

The STL’s stack has both inspectors, as empty() and top().

What does a list owe its callers? push() and pop(): are we done? We can add at the front and at the back, so there are two sets, one for each end. An iterator, to look through the items. Direct access to the first and the last item. Adding more than one item at a time? Concatenating lists? Splicing? Ranges? Then sorting: how do we sort a list?

Sorting is where completeness gets a sharp edge. When an operation is required but a generic algorithm can’t serve the structure efficiently, that operation becomes the structure’s own member. The STL’s std::sort needs random-access iterators; a linked list doesn’t have them, so the generic sort can’t touch it. Sorting is still a frequent need, so std::list carries its own sort.

Heaps have their own case. A heap is partially ordered, and many heaps are built on arrays. Such a heap can be sorted efficiently in place, and converting it to and from an array can be cheap, so the API should offer both.

A container’s own operations come from what it is, as the list shows. Taken as a whole, a container can also form one of the structures above, and then the math adds operations. The key word is under. An array is a monoid under concatenation, the way a number is one under + and another under *. Under other operations it forms other structures:

concat([1, 2], [3]); // [1, 2, 3]
add([1, 2], [3, 4]); // [4, 6]
dot([1, 2], [3, 4]); // 11
outer([1, 2], [3, 4]); // [[3, 4], [6, 8]]

Concatenation makes arrays, lists, and strings a monoid, with the empty sequence as its identity. Treated as vectors, arrays of one length are the objects of linear algebra. They add element by element, with an array of zeros as the identity and a negative for every array, and two of them multiply into a number (the dot product) or into a matrix (the outer product). A product that returns another type sits outside the ladder above, and linear algebra gives it laws of its own: the dot product, for one, is commutative and distributes over add. A type often has several views, and that is normal: we do not have to pick one. What we need is consistency, each view with operations that obey its laws.

For sets, the math prescribes most of the API, and JavaScript followed it. Over a fixed universe of values, sets form a semiring under union and intersection, as shown above, and a ring under symmetric difference and intersection, where every set is its own negative. The math prescribes union, intersection, difference, symmetric difference, complement, and the subset tests. JavaScript’s Set arrived in ES2015 with adding, deleting, lookup, and iteration. ES2025 added the math: union(), intersection(), difference(), symmetricDifference(), isSubsetOf(), isSupersetOf(), and isDisjointFrom(). Only the complement is missing: it needs a universe, and a Set has none.

Efficiency is part of completeness

Stepanov insisted on one more thing: the operations have to be efficient. Efficiency in the computational-complexity sense (the right big-O) is part of completeness. An operation that is present but quadratic where it could be linearithmic is only half there: it satisfies the signature and fails the use. A complete API states not just what each operation does, but, implicitly, what it costs.

In some cases efficiency dictates how an API is shaped. A famous example comes from Stepanov: should a list’s size() be O(1)? To tell how many nodes a list has, we count them, which is O(n). We can cache the count in a variable and update it on every push() and pop() at either end and on every concatenation, and then size() is O(1). That breaks one operation: extracting a sub-list defined by two nodes. In a doubly linked list it is O(1), a few links to change. With a cached size, we have to count the extracted nodes to update the sizes of both lists, which is O(k):

class List {
  // ... circular; push(), pop(), concat() update size
  extract(first, last) {
    // operation: the constant relink
    first.prev.next = last.next;
    last.next.prev = first.prev;
    first.prev = last;
    last.next = first;
    // housekeeping: the linear counting
    let k = 1;
    for (let node = first; node !== last; node = node.next) {
      ++k;
    }
    this.size -= k;
    // ... return first..last as a new list with size k
  }
}

So a constant-time operation becomes linear, to speed up a count we may never need. The simplest solution is to count nodes on demand. Stepanov argued the same: “if a user wants to keep a count it is easy to do, but usually you do not need it”. The standard committee overruled him, and std::list::size() is constant time.

The complete set has two layers. The first is operations enough to get from any valid state to any other. The second is frequent complex operations. Such an operation is not logically primitive: we could build it from the first layer, yet it is provided because callers need it often and a direct implementation beats the composition. It wins in one of two ways:

• Efficiency. The composition works, but it does more work than it has to.
• Correctness. The composition can be efficient, but it is hard to write correctly, and every caller who writes it takes that risk again.

sin is the familiar case, and it wins both ways. We can compute it ourselves through a series, but that is more code, it has precision problems to solve, and it is slower.

Replacing the top of a stack is a case of efficiency. Our app frequently pops the top and replaces it with a different value. It is simple to build from pop() and push(), but a direct write to the top is more efficient, if we need the speed:

class Stack {
  // ... (emptiness checks skipped for brevity)
  replaceTop(value) {
    const result = this.pop();
    this.push(value);
    return result;
  }
  replaceTopFast(value) {
    const topIndex = this.array.length - 1,
      result = this.array[topIndex];
    this.array[topIndex] = value;
    return result;
  }
}

On a heap the operation can be just as frequent, and it saves more. pop() and push() each restore the heap order, a pass of about log n steps, while replacing the top takes one pass.

Sorting a linked list is a case of correctness. It can be done efficiently through the prev and next links alone, but that takes thoughtful coding and debugging, so it belongs in the list’s API. Compound workflows fall here too: a frequent intent that takes a prescribed sequence of calls, each a chance to get it wrong. The balance’s deposit() and withdraw() beat balance -= amount in logging, in error messages, in atomicity, and in having one correct implementation. Node’s readFile() opens a file, reads it, and closes it in one call, so the common case has no close() to forget. Getting JSON from a server with fetch() takes four steps: call it, wait, check ok, then read the body. In my experience developers forget the ok check, and I have seen it in code review more than once. The fix is a helper or a method that does the whole sequence in one call, and a later post in this series takes such sequences up.

An operation belongs in the second layer when it is frequent and beats its composition in speed or in correctness.

Worked example: list-toolkit

My list-toolkit (zero-dependency list-based containers: circular singly and doubly linked lists, heaps, caches, queues, stacks, splay trees) applies these ideas in one library. The list questions above are its API: its lists carry their own sort(), and its array-based heap is built from an array in place (MinHeap.from()) and sorted in place back into one (releaseSorted()). Its heaps carry replaceTop(): the base class composes it from pop() and push(), and MinHeap overrides it with a single pass. Its lists count their nodes on demand, with getLength() at O(n), so extractRange() stays O(1). Two more things about it make the point.

The API is derived from axioms. Its Backgrounder opens by stating the axioms of a list (order is preserved unless modified, there is a first node and a last node, each node links to the next, the list is either circular or null-terminated) and the structural invariants in code (node.next.prev === node). The list operations follow from them. That is the domain prescribing the operation set, made concrete.

Completeness includes complexity. The Concepts: list API page annotates every method with its computational complexity: O(1), O(n), O(k). The efficiency point above, made literal.

The math stays underneath

Must our users learn algebra, then? No. On a custom charting library we ended up with 2D coordinates, geometric operations became matrices, and projections and directions were codified back to linear algebra. It helped us implement efficient algorithms and rethink what we needed in terms of an efficient API.

Our users were comfortable with geometry, and they wanted the API in geometric actions: move; rotate around a point; mirror around a line or around a point; scale along a line, or around a point vertically and horizontally.

In matrix terms each of those “complex” operations is one matrix, at the same cost as any other. Rotating around a point is three matrices composed: shift the point to the origin, rotate about the origin, and shift back. After multiplication it is a single matrix, applied to the array of points that makes a shape:

// shift to the origin, rotate, shift back: one matrix
const rotateAround = (p, angle) =>
  translate(p.x, p.y)
    .multiply(rotate(angle))
    .multiply(translate(-p.x, -p.y));

shape.transform(rotateAround(center, Math.PI / 4));

The users didn’t know that, but they used the canned actions and knew how to combine them into more complex ones. All of it was efficient matrix multiplication. Underneath, 2D affine transforms compose associatively, have an identity, and the useful ones invert; on top, the users saw the geometric verbs. Both describe the same operations.

Having a good math basis for the library, we implemented a complete set of operations, so our users could express their applications without restrictions. That is the other side of “we don’t support it” from the first post: nobody hits a wall the library could have anticipated.

Summary

Four things to take away:

• When a type is mathematical, its complete API is already written, with its correctness and costs; the work is to implement it. And it applies well beyond heavy math: a single balance needs the full set.
• Math gives a direction: implement an operation, and its complements and edge cases follow.
• Completeness has two layers: every valid state reachable from every other, plus the frequent operations that beat their composition, each at the right complexity. Those come in two kinds:
  • inefficient through the primitives, such as replaceTop();
  • hard to implement correctly, such as sorting a linked list.
• The users see their own domain’s verbs; the math stays underneath.

The next post takes another source of the complete shape, CRUD (create, read, update, delete) over objects and their collections, and shows it prescribes their API the same way math prescribes a number’s.