Weak and Strong Algebraic Structures
Weak and Strong Algebraic Structures
Hillel Wayne's recent newsletter on monoids got me thinking again about an old question of mine: why are some algebraic structures more useful than others in software applications?
A bit counterintuitively, a monoid is one of my examples of an algebraic structure that is not all that useful. A monoid is one of the simplest examples of an algebraic structure that programmers have a reason to talk about. In the context of implementing fold
, aka reduce
, in functional programming languages, if you recognize your input type as a monoid, then you can use a preexisting reduce
operator, and be confident it will work. One less for
loop to write.
Sadly, for monoids the story seems to end there. And this is where my curiosity comes in. If, by contrast, you recognized your data forms a vector space with a dot product (or you model it as one), then you open the door to a wealth of algorithms, data analysis techniques, and interpretations that you can bring to bear on a problem. You can compute various bases to represent your data efficiently, make sparse decompositions, project onto subspaces, compute distances, and study eigenvalues and eigenvectors.
Where are the useful algorithms for monoids? Where are the structure theorems? Surely there are some; an entire subfield of mathematics is devoted to monoid theory. But I haven't seen anything resembling a novel theorem about monoids used in a practical setting (please tell me if you know of one!).^{1}
My opinion on this has two parts. First, very few things are just monoids. Second, a monoid is just too weak of a structure to do anything really novel with.
For the first, consider the list of examples of monoids on Wikipedia. Out of these 19, there are only two examples that I'd consider "proper" monoids in that they have monoid structure but nothing more: the set of all finite strings over a given alphabet, and the set of all functions from a set to itself. The set of strings is a "free" monoid, meaning it is the unique monoid with the least possible extra structure.
All the others are either nonexamples (constructing a new monoid from an existing monoid) or describe sets that have more structure. E.g.,
 Every group/ring/field is a monoid
 The subsets of a set form a monoid, but they have the stronger structure of a lattice
 Functions into a structured set form a monoid, but usually more when the target of the function has more structure (e.g., the set of functions
X > R
is a ring whenR
is a ring).  The natural numbers (which form a monoid with zero as the additive identity) are usually better studied as integers, or modular integers, both of which form a ring.
 Sets with set union/intersection/complements are more structured than a monoid: they form a structure called a boolean algebra.
While they are monoids, most of these objects are not interesting for their monoid structure alone. The useful things about modular integers come from their group/ring/fieldtheoretic aspects, not their monoid structure.
For the second point, that a monoid is too weak, let me explain a bit about what I mean by "weak" and "strong."^{2} A "strong" structure admits constructive characterization theorems, and efficient algorithms to convert objects into various canonical forms. For example:
 Linear algebra: Gaussian elimination, the Jordan canonical form, QR decompositions, etc., which convert a matrix into a form that allows useful information to be trivially read from the canonical form (e.g., invertibility dimension, eigenvalues/eigenvectors, explicit dependences between rows).
 Graph theory: search algorithms, component decomposition, tree balancing, subgraph isomorphism (commonly used in computational chemistr; I'm working on a chapter of Practical Math on this very topic).
 Ring theory: residue number systems, the Euclidean algorithm, etc.
 Groups: the classification theorem of finite Abelian groups, algorithms on permutation groups.
These types of structures are useful because they give you new constructive things to latch an application on to. A graph, for example, has local structure in terms of node degree and subgraphs, along with global structure in terms of its component structure, degree distribution, and eigenvalue spectrum. Fields/rings let you factor things, compute inverses and GCDs, etc.
But what can you do with a monoid? Saying "you can reduce
it!" is saying little more than, "it is a monoid." When you reduce it, you don't actually use the monoid for anything more than its axiomatic definition, i.e., it's API. This is what I mean by "weak."
Another good example of a weak algebraic structure is a semilattice. Dataflow analysis in a compiler represents the data flowing through a program as a joinsemilattice, where the join operation represents how to combine two static estimates of a variable's value at a point where two branches of control flow join together. E.g., if you're estimating the possible range of an integer, you'd take a union of the two estimated ranges. It's a really neat idea, but if you look at the actual implementations of data flow analysis algorithms, they don't analyze the lattice in any meaningful way, they process a worklist of program points that need updating, and join lattice elements greedily. Like reduce
for monoids, it uses the algebraic "structure" not for any true structure, but for its API and local guarantees about it.
And this makes sense because it's not the lattice structure of the type that admits useful optimizations. Its the structure of the program being analyzed, like its particular combinations of control flow and branching, that matter. Similarly, a generic algorithm that processes lists isn't going to use any nontrivial monoid structure of its input types, but rather the special structure of the list instance given to it, such as knowntobesorted, or knowntobeuniqued etc. That's not to say that having a generic reduce
isn't nice; it is! It's just nice in its cleanliness, rather than allowing you to do something you couldn't do before.
Even groups, which I implied above are "strong," are really too weak to be useful in the same sense as linear algebra and rings/fields. Groups are mostly^{3} useful in computer science because they're weak enough that you can't easily crack cryptography based on them, but strong enough that you can define efficient encryption/decryption algorithms for them. If you set up a cryptosystem using the wrong group or the wrong public parameters, then the group has too much structure, becomes too easy to analyze, and the underlying security problem can be cracked.
Groups of numbers (or symmetries, or points on an elliptic curve) also have this nice property that they are compact. In a monoid like a string or a list, when you combine two elements z = xy
, you explicitly preserve the underlying elements x
and y
(though the dividing line is lost). This isn't forced by the definition of a monoid, but I find it curious that the "nontrivial" examples of monoidsbutnotmore are not compact in the same way as rings of numbers. Maybe monoids are weak because common monoids (that aren't spiritually more structured) are necessarily explicit, and hence the structure is already present in any representation as data, so there's no "new" structure to discover by an analogous kind of "change of basis" that you would find in linear algebra.
Other "weak" algebraic structures that I've never seen novel uses of: magma, groupoid, quandle (a sort of "group" that only has conjugation), and basically every structure listed in this diagram before "group."

I did read about "trace monoids" recently, which are apparently equivalent to dependency graphs. Wikipedia states: "Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while noncommuting letters stand for locks, synchronization points or thread joins....The utility of trace monoids comes from the fact that they are isomorphic to the monoid of dependency graphs; thus allowing algebraic techniques to be applied to graphs, and vice versa." However, I can't find any examples of these monoidalgebraic techniques applied to graphs. Most references seem to be unavailable, or quite old, which makes me suspect that people who study concurrent systems don't think about them as monoids. ↩

I don't like the terms "strong" and "weak" but I can't think of any better ones right now. I don't mean weak as in "bad," I mean weak as in "less rigid in constraining how the thing behaves." But somehow "rigid" and "loose" doesn't feel right, nor "strict" and "lenient." ↩

I am always interested in more constructive uses of group theory for practical programmers, but I have found very little. For some good examples, see this article on two's complement and this article on hashing unordered multisets, though both of those reinforce my point in that they rely on the groups being commutative, which in group theory entails a dramatically stronger structure, with the characterization theorems and efficient algorithms to back it up. ↩