Products and Coproducts

Bartosz Milewski · 2015 · Category Theory for Programmers, Ch. 5

Prereqs: 🍞 Chapter 1 (Category), 🍞 Chapter 2 (Types and Functions). 8 min.

Tuples and tagged unions aren't language features. They're universal constructions: the product is the best object with two projections, the coproduct is the best object with two injections. "Best" means every other candidate factors through it uniquely.

Initial and terminal objects

A terminal object has exactly one morphism coming from every other object. In sets, it's a singleton. In Python, it's None: every function can return None, and there's only one way to do it. An initial object has exactly one morphism going to every other object. In sets, it's the empty set. Both are unique up to isomorphism.

Scheme

; Terminal object: one morphism from every object to it.
; In Set, it's any singleton. In Scheme, we use '()
; unit : a -> ()
; There's exactly one such function for any type a.

(define (unit x) '())

(display "unit of 42:      ") (display (unit 42)) (newline)
(display "unit of 'hello:  ") (display (unit "hello")) (newline)
(display "unit of (list):  ") (display (unit (list 1 2 3))) (newline)
; Always '(). That's the point — there's only one morphism.

; Initial object: the empty set / Void.
; There's a unique morphism FROM it to every object,
; but you can never call it — there are no values of type Void.
(define (absurd x)
  (display "ERROR: Void has no values") (newline))

(display "absurd is defined but uncallable — Void is empty")

Universal construction — ranking candidates

Category theory defines objects by their relationships, not their internals. The universal construction is a three-step recipe: (1) define a pattern of objects and morphisms, (2) rank all candidates by whether one factors through another, (3) pick the best one. "Best" means every other candidate factors through it via a unique morphism.

Scheme

; Universal construction for products: find the "best" pair.
; Pattern: object c with two projections p: c->a, q: c->b.
;
; Candidate 1: c = (int, int, string), p = first, q = second
; Candidate 2: c = (int, int),         p = fst,   q = snd
;
; Candidate 2 is "better" because candidate 1 factors through it:
; there's a morphism m from candidate 1 to candidate 2
; such that p = fst . m and q = snd . m.

; Candidate 1: a triple (too much info)
(define (p-triple t) (car t))         ; first element
(define (q-triple t) (cadr t))        ; second element

; Candidate 2: a pair (just right)
(define (fst p) (car p))
(define (snd p) (cadr p))

; The factorizing morphism: strip the extra data
(define (m t) (list (car t) (cadr t)))

; Verify: p-triple = fst . m, q-triple = snd . m
(define test-triple (list 3 7 "extra"))

(display "p directly:   ") (display (p-triple test-triple)) (newline)
(display "fst . m:      ") (display (fst (m test-triple))) (newline)
(display "q directly:   ") (display (q-triple test-triple)) (newline)
(display "snd . m:      ") (display (snd (m test-triple))) (newline)
; The pair is better — the triple has redundant structure.

; Universal construction for products: find the "best" pair.
; Pattern: object c with two projections p: c->a, q: c->b.
;
; Candidate 1: c = (int, int, string), p = first, q = second
; Candidate 2: c = (int, int),         p = fst,   q = snd
;
; Candidate 2 is "better" because candidate 1 factors through it:
; there's a morphism m from candidate 1 to candidate 2
; such that p = fst . m and q = snd . m.

; Candidate 1: a triple (too much info)
(define (p-triple t) (car t))         ; first element
(define (q-triple t) (cadr t))        ; second element

; Candidate 2: a pair (just right)
(define (fst p) (car p))
(define (snd p) (cadr p))

; The factorizing morphism: strip the extra data
(define (m t) (list (car t) (cadr t)))

; Verify: p-triple = fst . m, q-triple = snd . m
(define test-triple (list 3 7 "extra"))

(display "p directly:   ") (display (p-triple test-triple)) (newline)
(display "fst . m:      ") (display (fst (m test-triple))) (newline)
(display "q directly:   ") (display (q-triple test-triple)) (newline)
(display "snd . m:      ") (display (snd (m test-triple))) (newline)
; The pair is better — the triple has redundant structure.

Products — tuples from projections

The product of objects a and b is an object c with two projections fst : c → a and snd : c → b, such that for any other candidate c' with projections p' and q', there exists a unique morphism m : c' → c where p' = fst ∘ m and q' = snd ∘ m. In programming, the product is a tuple.

Scheme

; Product = pair with projections fst and snd.
; The factorizer builds the unique morphism m.

(define (fst p) (car p))
(define (snd p) (cadr p))

; factorizer: given any two functions p: c->a and q: c->b,
; produce the unique m: c -> (a, b)
(define (factorizer p q)
  (lambda (x) (list (p x) (q x))))

; Example: c = integer, a = bool (is-even?), b = string (show)
(define (is-even? n) (= 0 (modulo n 2)))
(define (show n) (number->string n))

(define m (factorizer is-even? show))

(display "m(42):  ") (display (m 42)) (newline)
(display "m(7):   ") (display (m 7)) (newline)

; Verify: fst . m = is-even?, snd . m = show
(display "fst(m(42)) = is-even?(42)? ")
(display (equal? (fst (m 42)) (is-even? 42))) (newline)
(display "snd(m(42)) = show(42)?     ")
(display (equal? (snd (m 42)) (show 42)))
; The factorizer witnesses the universal property.

Coproducts — tagged unions from injections

Reverse the arrows and you get the coproduct. Instead of projections out, you have injections in: Left : a → c and Right : b → c. The universal property: for any other candidate c' with injections i' and j', there exists a unique morphism m : c → c' where i' = m ∘ Left and j' = m ∘ Right. In programming, the coproduct is Either (Haskell) or a tagged union.

Scheme

; Coproduct = Either = tagged union with Left and Right injections.

(define (Left x)  (list 'Left x))
(define (Right x) (list 'Right x))

(define (is-left? e)  (eq? (car e) 'Left))
(define (from-left e) (cadr e))
(define (from-right e) (cadr e))

; Coproduct factorizer: given i: a->c and j: b->c,
; produce the unique m: Either a b -> c
(define (factorizer-coprod i j)
  (lambda (e)
    (if (is-left? e)
        (i (from-left e))
        (j (from-right e)))))

; Example: convert either a number or a string to a display string
(define show-num (lambda (n) (string-append "Number: " (number->string n))))
(define show-str (lambda (s) (string-append "String: " s)))

(define m (factorizer-coprod show-num show-str))

(display (m (Left 42))) (newline)
(display (m (Right "hello"))) (newline)

; Verify: m . Left = show-num, m . Right = show-str
(display "m(Left(42)) = show-num(42)?      ")
(display (equal? (m (Left 42)) (show-num 42))) (newline)
(display "m(Right('hello')) = show-str('hello')? ")
(display (equal? (m (Right "hello")) (show-str "hello")))

; Coproduct = Either = tagged union with Left and Right injections.

(define (Left x)  (list 'Left x))
(define (Right x) (list 'Right x))

(define (is-left? e)  (eq? (car e) 'Left))
(define (from-left e) (cadr e))
(define (from-right e) (cadr e))

; Coproduct factorizer: given i: a->c and j: b->c,
; produce the unique m: Either a b -> c
(define (factorizer-coprod i j)
  (lambda (e)
    (if (is-left? e)
        (i (from-left e))
        (j (from-right e)))))

; Example: convert either a number or a string to a display string
(define show-num (lambda (n) (string-append "Number: " (number->string n))))
(define show-str (lambda (s) (string-append "String: " s)))

(define m (factorizer-coprod show-num show-str))

(display (m (Left 42))) (newline)
(display (m (Right "hello"))) (newline)

; Verify: m . Left = show-num, m . Right = show-str
(display "m(Left(42)) = show-num(42)?      ")
(display (equal? (m (Left 42)) (show-num 42))) (newline)
(display "m(Right('hello')) = show-str('hello')? ")
(display (equal? (m (Right "hello")) (show-str "hello")))

Duality — reverse the arrows

Every categorical construction has a dual: reverse all the arrows. The product's dual is the coproduct. The terminal object's dual is the initial object. Projections become injections. If you prove something about products, you get a theorem about coproducts for free. This is the power of the opposite category C^op.

Scheme

; Duality in action: product vs. coproduct side by side.
; Product:   c has fst: c->a, snd: c->b    (projections OUT)
; Coproduct: c has Left: a->c, Right: b->c  (injections IN)

; Product: decompose a pair
(define pair-val (list 3 7))
(display "Product:   fst=") (display (car pair-val))
(display ", snd=") (display (cadr pair-val)) (newline)

; Coproduct: construct a tagged value
(define (Left x)  (list 'Left x))
(define (Right x) (list 'Right x))
(display "Coproduct: Left(3)=")  (display (Left 3)) (newline)
(display "Coproduct: Right(7)=") (display (Right 7)) (newline)

; Product factorizer: two functions OUT => one function TO pair
; Coproduct factorizer: two functions IN => one function FROM either
; Same universal property, arrows reversed.

(display "Product factorizer:   c -> (a, b)") (newline)
(display "Coproduct factorizer: Either a b -> c") (newline)
(display "Dual constructions. Dual factorizers.")

Why products and coproducts aren't symmetric in Set

Functions must be defined on their entire domain but don't have to cover their codomain. This makes products and coproducts behave differently in the category of sets. A "bad" product candidate can lose information (too few projections), but a "bad" coproduct candidate can collapse information (map distinct values to the same output). The asymmetry comes from functions themselves, not from the constructions.

Scheme

; Asymmetry: a bad product candidate vs. a bad coproduct candidate.

; BAD product for (Int, Bool):
; c = Int, p = identity, q = is-even?
; This "works" but loses information — many ints map to the same bool.
; The real product (pair) doesn't lose anything.

(define (bad-p n) n)
(define (bad-q n) (= 0 (modulo n 2)))
(display "Bad product: (5, is-even?) = ")
(display (list (bad-p 5) (bad-q 5))) (newline)
(display "Can't recover the original bool from int alone.") (newline)
(newline)

; BAD coproduct for (Int, Bool):
; c = Int, i = identity, j = (lambda (b) (if b 1 0))
; This collapses: Left(1) and Right(#t) both map to 1.
; The real coproduct (Either) keeps them distinct.

(define (bad-i n) n)
(define (bad-j b) (if b 1 0))
(display "Bad coproduct: Left(1) = ") (display (bad-i 1)) (newline)
(display "Bad coproduct: Right(#t) = ") (display (bad-j #t)) (newline)
(display "Collision! Both map to 1. Either keeps them tagged and distinct.")

Notation reference

Blog / Haskell	Scheme	Meaning
()	'()	Terminal object (unit)
Void	(error ...)	Initial object (empty type)
fst :: (a, b) → a	(car p)	First projection
snd :: (a, b) → b	(cadr p)	Second projection
Left :: a → Either a b	(Left x)	Left injection
Right :: b → Either a b	(Right x)	Right injection
factorizer p q = \x → (p x, q x)	(factorizer p q)	Product factorizer
factorizer i j (Left a) = i a	(factorizer-coprod i j)	Coproduct factorizer

Neighbors

Milewski chapters

🍞 Chapter 4 — Kleisli Categories
🍞 Chapter 6 — Simple Algebraic Data Types (products + coproducts = algebra of types)

Paper pages that use products and coproducts

🍞 Hedges 2018 — open games use products for strategy profiles

Foundations (Wikipedia)

Translation notes

The blog post uses Haskell tuples and Either, plus C++ std::pair and tagged unions. This page uses Scheme lists as pairs and tagged lists as Either. The factorizers are direct translations of Milewski's Haskell definitions. The "ranking candidates" section (universal construction) is presented concretely: a triple is a worse product candidate than a pair because the triple factors through the pair. The blog post also discusses the asymmetry between products and coproducts in Set, which comes from functions being total (defined everywhere) but not necessarily surjective (covering the codomain).

Ready for the real thing? Read the blog post. The universal construction pattern here recurs in every chapter from here on.

← Kleisli Categories by june.kim Algebraic Data Types →