commit 476fac03ea40cc28644acb2fe6d63e80b406ab78
parent fac468b1a468da013d460b8b7d8ce1cbb47545e4
Author: Robert Russell <robert@rr3.xyz>
Date: Thu, 24 Sep 2026 09:50:56 -0700
Todo: more slop info
Diffstat:
| M | Todo/Algebra.slop.md | | | 131 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 131 insertions(+), 0 deletions(-)
diff --git a/Todo/Algebra.slop.md b/Todo/Algebra.slop.md
@@ -1,3 +1,5 @@
+# Long Discussion
+
## Summary
### 1. Initial objects
@@ -232,3 +234,132 @@
- **Ordered and topological:** preordered, ordered, linearly ordered and strictly ordered versions of semigroups, monoids, groups (bi- and left-ordered), abelian groups, semirings, rings, fields, modules, vector spaces and algebras; positive cones; group objects in Pos; topological monoids; topological and paratopological groups.
- **Categorical:** monoid, commutative monoid and group objects; category (monoidoid); semicategory; groupoid; core; ringoid; rigoid; rig (bimonoidal) category; monads; near-semiring objects (`Alternative`, `MonadPlus`); F-algebras and coalgebras; algebras for a monad; commutative theories and monads (bag vs. list); pointed sets with smash product; ringed spaces.
- **Examples:** ℕ, ℕ₊, ℕ∞, ℤ, ℚ, ℚ≥0, ℝ, ℝ≥0, ℂ, ordinals, polynomials, power series, matrices, quaternions, dual numbers, pointwise functions, computable reals, `Int`/`Word` (ℤ/2ⁿ), `Double`, `Bool`, permutations, valuation targets, multisets, sets, End(M), the {0, 1, t} rig, the Sorgenfrey line.
+
+# Algebraic Structures/Abstractions Useful in FP
+
+**Rule of thumb:** algebra pays off in FP when it gives you one of three things:
+- laws you can program against, which license folds, parallelism, incrementality, rewrites and property tests;
+- homomorphisms and free/quotient constructions;
+- order and fixpoint theory.
+
+Classification theory almost never pays off.
+
+**Cosets and ideals:** rarely used as such. What transfers is the general notion behind them: congruences and quotients (cosets are congruence classes; normal subgroups and ideals are kernels), plus orbits. Concrete cosets are elements of ℤ/n and syndrome decoding of linear codes. Ring ideals matter through quotient rings (§5). Order ideals (down-sets) matter in lattices and CRDTs (§7). Semigroup ideals show up as absorbing elements (§1).
+
+### 1. Extra laws on the basics
+- **Commutativity** → order-independent reduction: `HashMap`/bag folds that respect equality, and parallel partial results combined in completion order. Commutative effects can be reordered or batched (Haxl), and give exchangeability in probabilistic programs (Staton).
+- **Idempotence** (bands; plus commutativity = **semilattices**) → merging that tolerates duplicates and retries: state-based CRDTs, LVars, Datalog/Datafun, `Min`/`Max`, `First`/`Last`.
+- **Absorbing elements** → early exit from folds (`Any True`, `All False`, `0`); `empty <*> x = empty` → pruning in search.
+- **Cancellative, GCD and monus monoids** (`monoid-subclasses`) → `stripPrefix`/`isPrefixOf` for any monoid, parsers over any monoidal input (picoparsec), and multiset/`Natural` subtraction.
+- **Involutions/anti-homomorphisms** → `Dual . reverse` is a monoid iso `[a] → Dual [a]`; dagger and inverse categories model reversible and quantum languages.
+- **Near-semirings** → the actual laws of `Alternative`/`MonadPlus` (Rivas–Jaskelioff–Schrijvers).
+- **Closed (star) semirings, Kleene algebra (with tests)** → one matrix-closure algorithm gives shortest/widest paths, reachability, path counting and automaton→regex, just by swapping the semiring (Dolan, *Fun with Semirings*). Also: regex derivatives, semiring parsing (Goodman), provenance semirings, KAT/NetKAT verification.
+- **Graded monoids/rings** → `(++) :: Vec n a → Vec m a → Vec (n+m) a`; graded monads; units of measure (a ring graded by the dimension group).
+- **Preordered monoids/semirings** → effect systems via graded monads with subeffecting (Katsumata); usage multiplicities in QTT/Idris 2 ({0,1,ω}), Linear Haskell and Granule.
+- **Caveat:** IEEE `+`/`*` are only commutative magmas, so parallel float sums aren't reproducible and `Double` instances are only approximately lawful.
+
+### 2. Universal algebra (biggest payoff after the basics)
+- **Homomorphisms** → `foldMap f` is the unique monoid hom out of the free monoid. Homs parallelize (third homomorphism theorem, Gibbons) and justify fusion and GHC `RULES`. Monad morphisms give the laws for `lift` and `hoist`. `Traversable`'s naturality law quantifies over applicative homs.
+- **Free algebras** → the Boom hierarchy: free magma = leaf trees; add associativity = `NonEmpty`; add a unit = lists; add commutativity = bags; add idempotence = finite sets.
+ - Free group = reduced words.
+ - ℕ[X] = the universal provenance semiring.
+ - Free monads, applicatives and categories, with effect handlers = homs out of them (Plotkin–Pretnar).
+- **Initial algebras / final coalgebras** → ADTs and folds (recursion schemes); codata, streams and bisimulation.
+- **Presentations / equational theories** → algebraic effects = operations + equations (Plotkin–Power); Knuth–Bendix and rewriting; unification modulo AC/AG (F# units-of-measure inference, Maude, Tamarin).
+- **Birkhoff's HSP theorem** → equational laws survive products, subalgebras and quotients. So tuple and pointwise (`a -> b`) instances are lawful for free, and invariant-preserving newtypes inherit laws. Non-equational axioms don't survive:
+ - Fields aren't a variety: there is no free field, and pointwise `Fractional (a,b)` is unlawful because `(1,0)` has no inverse.
+ - Cancellativity isn't preserved by quotients.
+ - This is why `Group` makes `invert` an operation.
+- **Subalgebras** → a smart-constructor invariant is sound iff it is closed under every exported operation.
+- **Congruences and quotients** → `Eq` on an abstract type must be a congruence for its API. Also: quotient types (Lean `Quot`, cubical HITs, setoids), and e-graphs, which are incremental congruence closure. The 1st isomorphism theorem says you can represent A/ker f by im f, which is how normal forms work (sorted lists or `Map a Int` for bags, reduced words for free groups).
+- **Cayley's theorem** → difference lists (`Endo`), `Codensity` for monads (Rivas–Jaskelioff), CPS. All three reassociate for asymptotic speedups.
+- **Semidirect products** → pair a value with the transformation acting on it: diagrams (Yorgey, *Monoids: Theme and Variations*); rolling hashes and CRCs combine as affine maps x ↦ x·Bⁿ + h.
+
+### 3. Actions, torsors, automata
+- **Monoid actions** → update monads (Ahman–Uustalu); change actions/structures for incremental computation and semi-naïve Datalog (Alvarez-Picallo et al.; Cai et al.).
+- **Actions by homomorphisms** → lazy-propagation segment trees.
+- **Torsors / affine spaces** → points typed apart from differences: `UTCTime`/`NominalDiffTime`, pointer/offset (`vector-space`, `acts`).
+- **Transition monoids** → running a DFA is a hom into endofunctions on its states, which gives parallel/incremental lexing (Hillis–Steele; finger-tree measures).
+- **The bicyclic monoid** ⟨p,q ∣ pq=1⟩ → parallel bracket matching (Levien's "stack monoid").
+- **Orbits, stabilizers, Burnside** → quotient containers such as unordered pairs, bags and cycles (Abbott–Altenkirch–Ghani–McBride); species (Yorgey); symmetry reduction in search and model checking.
+- **Actions of monoidal categories** → profunctor optics are Tambara modules.
+
+### 4. Groups and their "-oids"
+- **Inverses** → range queries from prefix sums or Fenwick trees need inverses; segment trees need only a monoid. Also subtract-on-evict sliding windows, and undo.
+- **(Free) abelian groups** → Z-sets in DBSP and differential dataflow (incremental view maintenance with ± weights); units of measure (Kennedy).
+- **Cyclic groups** → wraparound indices, ring buffers (`Finite n`, `Mod m`).
+- **Symmetric groups** → permutations as invertible first-class data, axis transposes, species.
+- **Semigroupoids, categories, groupoids** (typed semigroups, monoids and groups) → the `semigroupoids` package; patches (Darcs; homotopical patch theory); HoTT identity types; isos.
+- **Inverse semigroups** (partial bijections) → partial isomorphisms for invertible parser/printers (Rendel–Ostermann); reversible computing.
+- **Trace (partially commutative) monoids** → Mazurkiewicz traces and partial-order reduction; scoped-label rows (Leijen; Koka effect rows).
+
+### 5. Rings and ideals
+- **Quotient rings in daily use:**
+ - ℤ/2ⁿ is wrapping `Word`/`Int`: a lawful ring, unlike `Double`. Odd numbers are units, which gives bijective hash mixers (SplitMix) and exact division by constants.
+ - ℤ/n with CRT and Fermat/Euler (Lagrange in the unit group) → modular types, multi-modular/NTT arithmetic, hashing.
+ - 𝔽₂[x]/(p) = GF(2ⁿ) → CRC (reduction is a ring hom, which gives `crc32_combine` and parallel CRC), Rabin fingerprints, Reed–Solomon, AES. The quotient is a field iff (p) is maximal iff p is irreducible.
+ - ℝ[ε]/(ε²) = dual numbers → forward-mode AD; ℝ[ε]/(εᵏ⁺¹) → Taylor-mode AD.
+- **Euclidean/GCD domains** → `semirings`' `GcdDomain`/`Euclidean`; generic extended gcd; canonical `Ratio`.
+- **Fields of fractions** → `Ratio a`, rational functions.
+- **Polynomial, power-series and monoid (semi)rings** → lazy power series (McIlroy). Convolution over a monoid unifies polynomials, languages and weighted automata (Elliott, *Generalized Convolution*).
+- **Noetherianity / ACC** → termination arguments: Kleene iteration terminates under ACC (otherwise you need widening), and Dickson/Hilbert make Buchberger's algorithm terminate.
+
+### 6. Modules & linear algebra
+- **Free semimodule monad** (finite S-weighted sums) → one monad with many semantics, depending on S:
+ - 𝔹 → nondeterminism
+ - ℕ → multisets
+ - ℝ≥0 → probability (distributions are free convex algebras)
+ - tropical → optimization
+ - ℂ → quantum amplitudes
+- **Matrices over semirings** → graph algorithms as linear algebra (GraphBLAS); weighted automata.
+- **Duals and transposes** → reverse-mode AD is transposed linearization (JAX, *You Only Linearize Once*; Elliott, *Simple Essence of AD*).
+- **𝔽₂-linear algebra** → XOR bases, linear codes.
+- **Tensor products, inner products, spectral theory, canonical forms, exterior/Clifford algebras** → numerics, ML and graphics only. Tensor products do serve as the model for monoidal products (§8).
+
+### 7. Order theory
+- **Complete lattices + Knaster–Tarski/Kleene** → semantics of recursion, dataflow analysis, Datalog, grammar analyses (nullable/FIRST).
+- **CPOs/domains** → semantics of laziness, ⊥ and general recursion.
+- **Galois connections** → abstract interpretation; calculating `floor`, integer division and integer sqrt (Backhouse; Mu–Oliveira).
+- **Distributive lattices, Birkhoff representation, down-sets** → causal histories and version vectors; join-irreducible decompositions for optimal delta-CRDT sync (Enes et al.).
+- **Boolean algebras** → bitsets, predicates, BDDs; set-theoretic types (CDuce, Elixir).
+- **Heyting algebras** → the intuitionistic logic of types.
+- **Security lattices** → information-flow control (LIO, MAC).
+- **Well-founded orders, WQOs, ordinals** → termination checking; homeomorphic embedding (Kruskal) as supercompilation's termination test.
+- **Quantales** → quantitative/metric semantics (niche).
+
+### 8. Categorified algebra (where all of the above resurfaces)
+- **Monoid objects:**
+ - `Monoid` under ×
+ - `Applicative` under Day convolution
+ - `Monad` under composition
+ - `Category`/`Arrow` in profunctors
+ - `Alternative` as a monoid on `f a`
+ - `Divisible`/`Decidable` as the contravariant versions
+- **Comonoids** → trivial in Hask, explicit under linearity (`linear-base`'s `Dupable`/`Consumable`).
+- **Eilenberg–Moore algebras** → monoids are list-monad algebras, convex sets are distribution-monad algebras; effect handlers.
+- **The rig of types up to iso** → "algebraic" data types, refactoring by algebra, zippers as derivatives and dissections (McBride); the reversible language Π as rig-groupoid isos (James–Sabry; Carette–Sabry).
+- **Distributive laws** (Beck) → when monads compose; `traverse`.
+- **Adjunctions** → free ⊣ forgetful underlies every "free X" above; `State` comes from currying.
+
+### 9. Little or no use
+These have little or no use:
+- Sylow theory, p-groups and the class equation
+- simple, solvable and nilpotent groups; composition series
+- the 2nd and 3rd isomorphism theorems
+- structure theorems for abelian groups and PID-modules; Jordan and rational canonical forms
+- field extensions and Galois theory
+- representation theory and Lie theory
+- homological algebra, most commutative algebra, algebraic geometry
+- subdirect representation, quasigroups
+- Green's relations and Krohn–Rhodes; Hopf algebras
+
+**Why:** these classify or decompose structures rather than supplying laws to program against, so they license no generic algorithm, data structure or rewrite.
+
+**Domain-specific exceptions:**
+- characters of finite abelian groups → FFT, NTT, Walsh–Hadamard
+- quaternions and SO(3) → graphics and robotics
+- Schreier–Sims → symmetry breaking (nauty)
+- Hermite and Smith normal forms → polyhedral compilation
+- Gröbner bases → computer algebra, nonlinear SMT, invariant generation
+
+I can turn this into a Doc if you want an editable catalogue.
