602: Product Types (Advanced)

Difficulty: 5 Level: Master Structs are categorical products: projections are field accessors, pairing morphisms are struct constructors, and lenses are the natural morphisms between products.

The Problem This Solves

You write structs every day, but treating them as categorical products unlocks a precise vocabulary for reasoning about data transformations. When is it safe to refactor a struct? When is two representations equivalent? When can you derive one accessor from others? Category theory answers these questions algebraically. The product type `A × B` is inhabited by pairs `(a, b)` where both an `A` and a `B` are present. Its projections `π₁: A×B → A` and `π₂: A×B → B` are field accessors. The universal property says: for any type `C` with functions `f: C→A` and `g: C→B`, there is a unique function `⟨f, g⟩: C → A×B`. This is exactly struct construction: `T { a: f(x), b: g(x) }`. Lenses emerge naturally from products: a lens for field `a` in `T { a: A, b: B }` is the pair of `get: T→A` (projection) and `set: A→T→T` (pairing with the other fields unchanged). Combining products and coproducts gives you the full algebraic type system.

The Intuition

A struct is a categorical product: `get` is a projection morphism, `set` is a pairing morphism that reconstructs the product, and Rust's struct update syntax `T { field: new, ..old }` is the categorical pairing — it applies the new projection for one field and the identity projection for all others. The trade-off: products give total access (all fields always present) but require updating all fields in transformations; coproducts give partial access but handle alternatives.

How It Works in Rust

// Product type A × B — both A and B are always present
struct Pair<A, B> {
 first: A,   // projection π₁
 second: B,  // projection π₂
}

impl<A, B> Pair<A, B> {
 // Universal property: unique morphism from C given f: C→A and g: C→B
 fn pair<C>(c: C, f: impl Fn(&C) -> A, g: impl Fn(&C) -> B) -> Self {
     Pair { first: f(&c), second: g(&c) }
 }

 // Lens for `first`: get + set
 fn get_first(&self) -> &A { &self.first }

 fn set_first(self, new_first: A) -> Self {
     Pair { first: new_first, ..self }  // struct update = categorical pairing
 }

 // Bifunctor: map both components independently
 fn bimap<C, D>(self, f: impl FnOnce(A) -> C, g: impl FnOnce(B) -> D) -> Pair<C, D> {
     Pair { first: f(self.first), second: g(self.second) }
 }
}

// Algebraic identity: A × () ≅ A
fn from_unit_pair<A>(p: Pair<A, ()>) -> A { p.first }
fn to_unit_pair<A>(a: A) -> Pair<A, ()> { Pair { first: a, second: () } }

// Record update syntax IS the pairing morphism
#[derive(Clone)]
struct Config { host: String, port: u16, tls: bool }

let base = Config { host: "localhost".into(), port: 8080, tls: false };
let prod = Config { port: 443, tls: true, ..base };  // pairing: new π_port, π_tls; identity π_host

What This Unlocks

Lens derivation: any field in a struct has a canonical lens — `get` = projection, `set` = pairing. This is how optics libraries like `lens-rs` are derived.
Type algebra: refactor `(A, B, C)` to `((A, B), C)` — the isomorphism is `((a, b), c) ↔ (a, b, c)`, useful for generic code that works on nested products.
Generic programming: functions that work on "any product with a `name` field" are expressed as trait bounds — the typeclass approach to structural polymorphism.

Key Differences

Concept	OCaml	Rust
Product A×B	`type t = { a: A; b: B }`	`struct T { a: A, b: B }`
Projection π₁	`.a` field access	`.a` field access
Projection π₂	`.b` field access	`.b` field access
Pairing morphism	`{ a = f x; b = g x }`	`T { a: f(x), b: g(x) }`
Record update	`{ r with a = v }`	`T { a: v, ..r }`
Lens	`{get; set}` record	`(fn get, fn set)` or lens struct
Unit product	`unit` / `()`	`()`

#[derive(Debug,Clone,Copy,PartialEq)]
struct Point { x: f64, y: f64 }

#[derive(Debug,Clone,Copy)]
struct Rect { origin: Point, size: Point }

// Projections
fn proj_x(p: Point) -> f64 { p.x }
fn proj_y(p: Point) -> f64 { p.y }

// Record update: categorical pairing
fn translate(dx: f64, dy: f64, p: Point) -> Point { Point { x: p.x+dx, y: p.y+dy } }
fn scale(s: f64, p: Point) -> Point { Point { x: p.x*s, y: p.y*s } }

// Product bifunctor
fn bimap<A,B,C,D>(f: impl Fn(A)->C, g: impl Fn(B)->D, (a,b): (A,B)) -> (C,D) { (f(a), g(b)) }

// Associativity iso: (A×B)×C ≅ A×(B×C)
fn assoc_l<A,B,C>((a,b,c): (A,B,C)) -> (A,(B,C)) { (a,(b,c)) }
fn assoc_r<A,B,C>((a,(b,c)): (A,(B,C))) -> (A,B,C) { (a,b,c) }

// Swap: A×B ≅ B×A
fn swap<A,B>((a,b): (A,B)) -> (B,A) { (b,a) }

// Universal property: diagonal morphism
fn diag<A: Copy>(a: A) -> (A,A) { (a,a) }

fn main() {
    let p = Point { x:1.0, y:2.0 };
    let p2 = translate(3.0, 4.0, p);
    println!("translated: {:?}", p2);
    println!("scaled: {:?}", scale(2.0, p));

    let r = Rect { origin: p, size: Point{x:10.0,y:5.0} };
    // Record update: only change origin
    let moved = Rect { origin: translate(1.0,0.0,r.origin), ..r };
    println!("moved rect origin: {:?}", moved.origin);

    let result = bimap(|x:i32| x*2, |s: &str| s.len(), (5,"hello"));
    println!("bimap: {:?}", result);

    let triple = (1,2,3);
    println!("assoc_l: {:?}", assoc_l(triple));
    println!("assoc_r: {:?}", assoc_r(assoc_l(triple)));
    println!("swap: {:?}", swap((1,"a")));
    println!("diag: {:?}", diag(42));
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn translate_test() { let p=translate(1.0,2.0,Point{x:0.0,y:0.0}); assert_eq!((p.x,p.y),(1.0,2.0)); }
    #[test] fn assoc_roundtrip() { let t=(1,2,3); assert_eq!(assoc_r(assoc_l(t)),t); }
    #[test] fn swap_swap() { let p=(1,"a"); assert_eq!(swap(swap(p)),p); }
}

(* Product types and record update in OCaml *)
type point = { x: float; y: float }
type rect  = { origin: point; size: point }

(* Projections *)
let fst_point { x; _ } = x
let snd_point { y; _ } = y

(* Pairing morphism *)
let make_point x y = { x; y }

(* Record update *)
let translate dx dy p = { p with x=p.x+.dx; y=p.y+.dy }
let scale     s     p = { x=p.x*.s; y=p.y*.s }

(* Product bifunctor *)
let bimap f g (a,b) = (f a, g b)

(* Associativity via isomorphism *)
let assoc_l ((a,b),c) = (a,(b,c))
let assoc_r (a,(b,c)) = ((a,b),c)

let () =
  let p = make_point 1. 2. in
  let p2 = translate 3. 4. p in
  Printf.printf "(%.1f,%.1f)\n" p2.x p2.y;
  let scaled = scale 2. p in
  Printf.printf "scaled=(%.1f,%.1f)\n" scaled.x scaled.y;
  let (a,b) = bimap (fun x->x*2) (fun s->String.length s) (5,"hello") in
  Printf.printf "bimap=(%d,%d)\n" a b