April 23, 2026
When Lists Become Bits
Prefix-freeness is the property that lifts the free-monoid construction into bit space.
Monoids
Browse posts by tag
March 13, 2026
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.
March 13, 2026
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.
March 13, 2026
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.
January 18, 2026
Seeing Structure First
A reflection on eleven explorations in generic programming, and how algorithms arise from algebraic structure.
March 15, 2019
One Algorithm, Infinite Powers
The Russian peasant algorithm computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.