Free Algebras: Why Lists and Polynomials Are Universal
Lists are everywhere in programming. Not because they are convenient. Because they are algebraically universal.
Why Lists?
Arrays are more cache-friendly. Hash maps have better lookup. Yet lists (sequences, vectors, streams) remain the default container in nearly every language. The standard explanation is convention, or ease of construction. The real explanation is algebraic.
A list is the free monoid. It is the most general monoid you can build from a set of generators. And the universal property of free monoids says that fold, the operation that processes a list element by element, is not a design pattern. It is a theorem.
The Free Monoid
Start with a set \(S\) of generators. The free monoid on \(S\) is the set of all finite sequences of elements from \(S\), with concatenation as the operation and the empty sequence as the identity.
“Free” means: no equations hold except those forced by the monoid axioms (associativity and identity). In particular:
- \([a, b] \neq [b, a]\). Commutativity is not imposed.
- \([a, a] \neq [a]\). Idempotency is not imposed.
- \([a, b, c] = [a] \cdot [b] \cdot [c]\). Every sequence is a product of singletons.
In C++:
template<typename T>
class free_monoid {
std::vector<T> elements_;
public:
free_monoid() = default;
explicit free_monoid(T x) : elements_{std::move(x)} {}
// ...
};
// Monoid operations via ADL
template<typename T>
free_monoid<T> op(const free_monoid<T>& a, const free_monoid<T>& b); // concatenation
template<typename T>
free_monoid<T> identity(const free_monoid<T>&); // empty sequence
The free_monoid<int> is the type of finite sequences of integers. Its operation is concatenation. It satisfies the Monoid concept. And it is the most general monoid on int: no structure beyond associativity and identity.
The Universal Property
Here is the key fact. Given any function \(f: S \to M\) where \(M\) is a monoid, there exists a unique monoid homomorphism \(\overline{f}: \text{Free}(S) \to M\) extending \(f\). This homomorphism is defined by:
$$\overline{f}([a_1, a_2, \ldots, a_n]) = f(a_1) \cdot f(a_2) \cdot \ldots \cdot f(a_n)$$In code:
template<Monoid M, typename T, typename F>
M extend(F f, const free_monoid<T>& xs) {
M result = identity(M{});
for (const auto& x : xs.elements())
result = op(result, f(x));
return result;
}
This is fold. The universal property says fold is the only structure-preserving way to interpret a list in a monoid. Any function that respects the monoid structure must agree with fold.
Fold Is a Theorem
When you write std::accumulate or std::reduce, you are invoking the universal property. The homomorphism condition:
