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 recursively collapses a fixed-point structure into the carrier. It peels off one layer with unfix, recursively processes all sub-structures with fmap, then applies the evaluator. This is the unique homomorphism guaranteed by initiality.
# Catamorphism: the universal folddef fix(x): return ("fix", x)
def unfix(x): return x[1]
def natf_map(f, x):
if x[0] == "zero": return x
return ("succ", f(x[1]))
def cata(fmap, alg, x):
return alg(fmap(lambda y: cata(fmap, alg, y), unfix(x)))
# Build naturals
zero = fix(("zero",))
def succ(n): return fix(("succ", n))
three = succ(succ(succ(zero)))
# Count algebradef count_alg(x):
return0if x[0] == "zero"else1 + x[1]
print(f"cata count 3: {cata(natf_map, count_alg, three)}")
# Fibonacci algebradef fib_alg(x):
if x[0] == "zero": return (1, 1)
a, b = x[1]
return (b, a + b)
six = succ(succ(succ(three)))
print(f"fib(6): {cata(natf_map, fib_alg, six)[0]}")
Lists as an initial algebra
Lists are the initial algebra of ListF e a = Nil | Cons e a. The catamorphism over ListF is foldr. Every fold you've ever written is a catamorphism in disguise.
Scheme
; ListF e a = Nil | Cons(e, a); Represented as ('nil) or ('cons element rest)
(define (listf-map f x)
(if (eq? (car x) 'nil) x
(list 'cons (cadr x) (f (caddr x)))))
; Build a list: [10, 20, 30]
(define (fix-nil) (fix '(nil)))
(define (fix-cons e rest) (fix (list 'cons e rest)))
(define my-list
(fix-cons 10 (fix-cons 20 (fix-cons 30 (fix-nil)))))
; Algebra 1: sum โ ListF(Int, Int) -> Int
(define (sum-alg x)
(if (eq? (car x) 'nil) 0
(+ (cadr x) (caddr x))))
(display "sum [10,20,30]: ")
(display (cata listf-map sum-alg my-list)) (newline)
; Algebra 2: length โ ListF(Int, Int) -> Int
(define (len-alg x)
(if (eq? (car x) 'nil) 0
(+ 1 (caddr x))))
(display "length [10,20,30]: ")
(display (cata listf-map len-alg my-list)) (newline)
; Algebra 3: collect to native list
(define (to-list-alg x)
(if (eq? (car x) 'nil) '()
(cons (cadr x) (caddr x))))
(display "to-list: ")
(display (cata listf-map to-list-alg my-list))
; foldr IS cata. Every fold is a catamorphism.
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 (syntax). Different algebras over the same functor give different interpretations (semantics). Here: ring expressions can be evaluated to integers, pretty-printed to strings, or simplified, all via different algebras over the same RingF functor.
The blog post uses Haskell's type system to enforce the functor constraint on cata and to distinguish Fix from unFix at the type level. In Scheme, fix and unfix are just list wrappers; the functor map is passed explicitly. The blog post covers infinite structures via coalgebras (streams, the Sieve of Eratosthenes). This page limits coalgebras to finite unfolding because BiwaScheme does not support lazy evaluation. The blog post also proves that Lambek's theorem follows from initiality: the inverse of the evaluator is itself an algebra homomorphism, so it must be unique, making the evaluator an isomorphism. That proof is structural, not computational, so it 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