Browse posts by tag
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.
A homomorphism preserves structure. fold is the universal homomorphism from the free monoid. This is the algebraic reason that fold, evaluation, and parallelism work.
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.
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.
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.
A reflection on eleven explorations in generic programming, and how algorithms arise from algebraic structure.
18-part lecture series on efficient programming. Covers the intellectual foundations behind STL.
Collected notes on programming philosophy. Free PDF.
Blends discrete mathematics with analysis and algorithm design.
Rigorous foundations of generic programming. Connects algebra and algorithms. Stepanov’s magnum opus.
History of mathematical ideas underlying generic programming. More accessible than EoP.
Broad coverage of numerical algorithms in science and engineering. Classic cross-topic numerical algorithms.
Classic talk on recognizing algorithmic patterns. ‘No raw loops’ - shows how rotate solves many problems elegantly.
AlgoGraph is an immutable graph library for Python with pipe-based transformers, declarative selectors, and lazy views.
The Stepanov series showed that algorithms arise from algebraic structure. This post is about the flip side: sometimes you choose a different structure to make the algorithm trivial.
Graduate problem set solutions in computational statistics and numerical methods from my math master's at SIUe. Implementing things from scratch teaches you what the libraries are hiding.
The Miller-Rabin primality test demonstrates how probabilistic algorithms achieve arbitrary certainty, trading absolute truth for practical efficiency.
The Russian peasant algorithm computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.
Bloom filters trade perfect recall for extraordinary space efficiency. How they work and why they matter.