An F-algebra is a functor F plus a morphism F(a) → a. The initial algebra is the fixed point of the functor: it is the recursive data type. A catamorphism (fold) is the unique morphism from the initial algebra to any other algebra. Every recursive data type you define is an initial algebra. Every fold you write is a catamorphism.
What is an F-algebra
An F-algebra has three parts: an endofunctor F (the shape of one layer of recursion), a carrier object a (the result type), and an evaluator F(a) → a (how to collapse one layer). The functor generates expressions; the evaluator interprets them.
Scheme
; An F-algebra = (functor, carrier, evaluator); The functor describes one layer of a recursive type.; The evaluator collapses that layer into the carrier.; NatF: the functor for natural numbers.; NatF(a) = Zero | Succ(a); Represented as tagged lists: ('zero) or ('succ value)
(define (natf-map f x)
(if (eq? (car x) 'zero)
x
(list 'succ (f (cadr x)))))
; An algebra over NatF with carrier = integer; Evaluator: NatF(Int) -> Int
(define (eval-int x)
(if (eq? (car x) 'zero) 0
(+ 1 (cadr x))))
(display "eval Zero: ")
(display (eval-int '(zero))) (newline)
(display "eval Succ(0): ")
(display (eval-int (list 'succ 0))) (newline)
(display "eval Succ(2): ")
(display (eval-int (list 'succ 2)))
; Each call collapses ONE layer. Not recursive yet.
A recursive data type is the fixed point of its functor: Fix f = f (Fix f). Wrapping with Fix lets you nest layers infinitely. The fixed point is the initial algebra: there is exactly one algebra homomorphism from it to any other algebra. Lambek's theorem says the initial algebra's evaluator is an isomorphism: F(Fix f) ≅ Fix f.
Scheme
; Fix f = f (Fix f); We represent Fix as nested tagged lists.; fix wraps one layer, unfix unwraps it.
(define (fix x) (list 'fix x))
(define (unfix x) (cadr x))
; Build natural numbers from NatF
(define zero (fix '(zero)))
(define (succ n) (fix (list 'succ n)))
(define one (succ zero))
(define two (succ one))
(define three (succ two))
(display "zero: ") (display zero) (newline)
(display "one: ") (display one) (newline)
(display "two: ") (display two) (newline)
(display "three: ") (display three)
; Each number is layers of Fix wrapped around NatF.; fix and unfix are inverses โ that's Lambek's theorem.
Catamorphisms โ the universal fold
A catamorphism takes an algebra (evaluator) and collapses a fixed-point structure into the carrier. It peels off one layer with unfix, processes all sub-structures recursively with fmap, then applies the evaluator. This is the unique homomorphism guaranteed by initiality.
An F-coalgebra reverses the arrow: a → F(a). Instead of collapsing structure, it generates it. The terminal coalgebra is the greatest fixed point. The anamorphism (unfold) is the unique morphism into the terminal coalgebra. In Haskell, the fixed point for both is Fix f, but conceptually: algebras consume, coalgebras produce.
Scheme
; Anamorphism: unfold from a seed.; ana : (a -> F(a)) -> a -> Fix(F); ana coalg = fix . fmap (ana coalg) . coalg
(define (ana fmap coalg seed)
(fix (fmap (lambda (s) (ana fmap coalg s))
(coalg seed))))
; Coalgebra: generate natural numbers from an int; Int -> NatF(Int)
(define (nat-coalg n)
(if (= n 0) '(zero)
(list 'succ (- n 1))))
(display "ana 3: ")
(display (ana natf-map nat-coalg 3)) (newline)
; Builds the same structure as (succ (succ (succ zero))); Round trip: ana builds, cata tears down
(display "cata count (ana 5): ")
(display (cata natf-map count-alg (ana natf-map nat-coalg 5))) (newline)
; Coalgebra for lists: generate from a native list
(define (list-coalg xs)
(if (null? xs) '(nil)
(list 'cons (car xs) (cdr xs))))
(define built (ana listf-map list-coalg '(123)))
(display "round-trip [1,2,3]: ")
(display (cata listf-map to-list-alg built))
; ana . cata = identity on the fixed point.
Ring expressions โ algebras as evaluators
F-algebras cleanly separate syntax from semantics. The functor defines the shape of expressions; different algebras over the same functor give different interpretations. Ring expressions can be evaluated to integers, pretty-printed to strings, or simplified, all by swapping the algebra.
Haskell's type system enforces the functor constraint on cata and distinguishes Fix from unFix at the type level. In Scheme, fix and unfix are just list wrappers; the functor map is passed explicitly. The original post covers infinite structures via coalgebras (streams, the Sieve of Eratosthenes); this page limits coalgebras to finite unfolding because BiwaScheme lacks lazy evaluation. Milewski also proves that Lambek's theorem follows from initiality: the inverse of the evaluator is itself an algebra homomorphism, so it must be unique, and the evaluator is therefore an isomorphism. That proof is structural, not computational, and does not translate to runnable code.
Ready for the real thing? Read the blog post. Start with the definition of Algebra, then trace how Fix and cata fall out of initiality.
F-algebra