Category Theory for Algebra

Haskell , a language with 10,000+ packages , is built on category theory: monads, functors, applicatives are mathematical structures from category theory. Rust enums and structs are literally categorical sums and products. Folding a list is a universal catamorphism , a theorem of category theory.

• **Haskell/Rust types:** Maybe, Either, List are initial algebras in the category of types; functor laws are theorems of category theory
• **Compiler optimizations:** GHC uses initial algebra theory for deforestation , eliminating intermediate data structures via fold/build fusion
• **Databases:** functors describe schema mappings; migrations are natural transformations; relational algebra is a categorical structure

Предварительные знания

• Galois Theory

Functors in Algebra

Haskell , a language with 10,000+ packages , is built on category theory: monads, functors, applicatives are mathematical structures from category theory. A functor F: C → D is a structure-preserving map between categories: objects to objects, morphisms to morphisms, preserving composition and identity. The forgetful functor Grp → Set drops algebraic structure; the free functor Set → Grp builds free groups.

In Haskell: `fmap` for `Maybe`, `[]`, `IO` is a functor in the categorical sense. Functor laws: fmap id = id and fmap (f . g) = fmap f . fmap g. The Haskell typeclass Functor encodes exactly these two laws.

Universal Algebra

Universal algebra studies algebraic structures via signatures and equational theories. A variety is a class of algebraic structures defined by equations. Groups, rings, and lattices are varieties. Birkhoff's theorem: a class of algebras is a variety if and only if it is closed under homomorphic images, subalgebras, and direct products (the HSP theorem).

**Examples of varieties:** groups (6 equations), abelian groups (+1 equation), rings (12 equations), Boolean algebras (finitely many equations). Non-variety: finite groups , closure under direct products fails (∏ ℤ/nℤ is infinite).

Algebraic Data Types and Initial Algebras

Algebraic data types (ADTs) in Haskell/Rust are literally algebra: product types (A × B, struct/tuple) and sum types (A + B, enum/Either). Natural numbers are the initial algebra for the functor F(X) = 1 + X: ℕ = Fix(F) = 1 + (1 + (1 + ...)). Lists are the initial algebra for F(X) = 1 + A×X. This is not a metaphor , it is a theorem of category theory.

**Lambek's theorem:** if (A, α: FA → A) is an initial F-algebra, then α is an isomorphism. This means A ≅ F(A) , a recursive type equation. For ℕ: ℕ ≅ 1 + ℕ (zero or successor). For List[a]: List[a] ≅ 1 + a × List[a] (empty or head plus tail).

Key Ideas

• **Functors:** F: C→D preserves objects, morphisms, composition and identity; Free ⊣ Forget is the archetypal adjunction; fmap in Haskell is a functor
• **Universal algebra:** a variety = class defined by equations = HSP-closed class; associativity and commutativity are both equations
• **ADTs and initial algebras:** ℕ = Fix(1+X), List[A] = Fix(1+A×X); fold = catamorphism = unique homomorphism from the initial algebra
• **Products and sums:** A×B (struct/tuple), A+B (enum/Either); categorical constructions behind everyday data types

Related Topics

Category theory unifies all of algebra:

• Group theory — Groups are objects in the category Grp; functors between algebras are homomorphisms; Free ⊣ Forget adjunction
• Galois theory — The Galois correspondence is an anti-equivalence of categories: subfields map to subgroups contravariantly

Вопросы для размышления

• A monad in Haskell is a monoid in the category of endofunctors. What does this mean concretely: what are the 'multiplication' and 'unit' of a monad, and how do they relate to bind (>>=) and return?
• Fix f in Haskell is the initial algebra of functor f. Write the binary tree type via Fix and implement fold (catamorphism) for it.
• Covariant vs contravariant functors: Hom(A, -) is covariant, Hom(-, B) is contravariant. How does this connect to the fact that Rust function types Fn(A) -> B are covariant in B and contravariant in A?