247 Expert

Limits and Colimits

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Limits and Colimits" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Limits and colimits are the categorical generalizations of "greatest lower bounds" and "least upper bounds." Products, terminal objects, equalizers, and pullbacks are all limits; coproducts, initial objects, coequalizers, and pushouts are all colimits. Key difference from OCaml: | Concept | Rust | OCaml |

Tutorial

The Problem

Limits and colimits are the categorical generalizations of "greatest lower bounds" and "least upper bounds." Products, terminal objects, equalizers, and pullbacks are all limits; coproducts, initial objects, coequalizers, and pushouts are all colimits. In type theory and functional programming, they correspond to familiar constructs: product types (limits), sum types (colimits), function spaces, and more. This example instantiates categorical limits and colimits as Rust types and shows the universal property that characterizes each.

🎯 Learning Outcomes

• Identify products, coproducts, equalizers, and pullbacks as categorical limits/colimits

• Implement the universal property (unique morphism) for products and coproducts in Rust

• See how (A, B) is the limit of the diagram A ← • → B

• See how Either<A, B> is the colimit of the same diagram

• Compare categorical constructions with OCaml's type-theoretic encodings

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Limits and colimits are universal constructions in category theory.
   Products = binary limits; Coproducts = binary colimits.
   In types: products = tuples, coproducts = sum types *)

(* Product = limit of discrete diagram {A, B} *)
(* Characterised by projections fst, snd *)
let product_intro a b = (a, b)
let fst (a, _) = a
let snd (_, b) = b

(* Universality: any cone factors uniquely through the product *)
let pair_of f g x = (f x, g x)

(* Coproduct = colimit of discrete diagram {A, B} *)
type ('a, 'b) coprod = Inl of 'a | Inr of 'b

let coprod_inl a = Inl a
let coprod_inr b = Inr b

(* Universality: any cocone factors through the coproduct *)
let coprod_elim f g = function Inl a -> f a | Inr b -> g b

(* Equaliser = limit of parallel arrows *)
(* { x | f(x) = g(x) } *)
let equaliser f g lst = List.filter (fun x -> f x = g x) lst

(* Coequaliser = colimit *)
(* Quotient: identify elements where f(x) = f(y) -> same class *)
let coequaliser f lst =
  let module M = Map.Make(Int) in
  List.fold_left (fun m x -> M.add (f x) x m) M.empty lst
  |> M.bindings |> List.map snd

let () =
  Printf.printf "product (3,4): fst=%d snd=%d\n" (fst (3,4)) (snd (3,4));

  let both = pair_of (fun x -> x * 2) (fun x -> x + 10) in
  Printf.printf "pair_of: %s\n" (let (a,b) = both 5 in Printf.sprintf "(%d,%d)" a b);

  let sum_or_str = coprod_elim string_of_int (fun s -> s ^ "!") in
  Printf.printf "coprod Inl 42: %s\n" (sum_or_str (Inl 42));
  Printf.printf "coprod Inr hi: %s\n" (sum_or_str (Inr "hi"));

  let eq = equaliser (fun x -> x mod 2) (fun x -> x mod 3) [0;1;2;3;4;5;6;12] in
  Printf.printf "equaliser mod2=mod3: [%s]\n" (eq |> List.map string_of_int |> String.concat ";")

Key Differences

Concept	Rust	OCaml
Product	`(A, B)` tuple	record or tuple
Coproduct	`enum Either<A,B>`	`type ('a,'b) either`
Terminal	`()` unit	`unit`
Initial	`!` (never, unstable)	`type empty = \\|`
Equalizer	`Vec` filter	`List.filter`
Pullback	nested filter	`List.concat_map`

Limits/colimits are why product types and sum types look the way they do: they are the unique objects satisfying universal properties up to isomorphism.

OCaml Approach

OCaml types directly embody limits and colimits:

(* Product = record/tuple *)
let product_univ fst snd c = (fst c, snd c)

(* Coproduct = variant *)
let coprod_univ inl inr = function
  | Left a  -> inl a
  | Right b -> inr b

(* Equalizer = filtered list via List.filter *)
let equalizer f g xs = List.filter (fun x -> f x = g x) xs

(* Pullback = cartesian product filtered *)
let pullback f g xs ys =
  List.concat_map (fun x ->
    List.filter_map (fun y ->
      if f x = g y then Some (x, y) else None) ys) xs

OCaml's type system makes the connection more transparent; Rust requires more scaffolding to express the same categorical ideas.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Limits and colimits are universal constructions in category theory.
   Products = binary limits; Coproducts = binary colimits.
   In types: products = tuples, coproducts = sum types *)

(* Product = limit of discrete diagram {A, B} *)
(* Characterised by projections fst, snd *)
let product_intro a b = (a, b)
let fst (a, _) = a
let snd (_, b) = b

(* Universality: any cone factors uniquely through the product *)
let pair_of f g x = (f x, g x)

(* Coproduct = colimit of discrete diagram {A, B} *)
type ('a, 'b) coprod = Inl of 'a | Inr of 'b

let coprod_inl a = Inl a
let coprod_inr b = Inr b

(* Universality: any cocone factors through the coproduct *)
let coprod_elim f g = function Inl a -> f a | Inr b -> g b

(* Equaliser = limit of parallel arrows *)
(* { x | f(x) = g(x) } *)
let equaliser f g lst = List.filter (fun x -> f x = g x) lst

(* Coequaliser = colimit *)
(* Quotient: identify elements where f(x) = f(y) -> same class *)
let coequaliser f lst =
  let module M = Map.Make(Int) in
  List.fold_left (fun m x -> M.add (f x) x m) M.empty lst
  |> M.bindings |> List.map snd

let () =
  Printf.printf "product (3,4): fst=%d snd=%d\n" (fst (3,4)) (snd (3,4));

  let both = pair_of (fun x -> x * 2) (fun x -> x + 10) in
  Printf.printf "pair_of: %s\n" (let (a,b) = both 5 in Printf.sprintf "(%d,%d)" a b);

  let sum_or_str = coprod_elim string_of_int (fun s -> s ^ "!") in
  Printf.printf "coprod Inl 42: %s\n" (sum_or_str (Inl 42));
  Printf.printf "coprod Inr hi: %s\n" (sum_or_str (Inr "hi"));

  let eq = equaliser (fun x -> x mod 2) (fun x -> x mod 3) [0;1;2;3;4;5;6;12] in
  Printf.printf "equaliser mod2=mod3: [%s]\n" (eq |> List.map string_of_int |> String.concat ";")

Deep Comparison

OCaml vs Rust: Limits Colimits

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement a type-level product and coproduct using a custom Either<L,R> enum and verify the universal property functions type-check.

Encode the pushout (dual of pullback) as a type: given A <- C -> B, the pushout is a type that merges A and B while identifying the images of C.

Show that Option<A> is the coproduct A + () by implementing from_option and to_option witnessing the isomorphism.

Implement the limit of a chain diagram A₀ <- A₁ <- A₂ <- ... (inverse limit) as a type of compatible sequences.

Prove that right adjoints preserve limits and left adjoints preserve colimits by showing a concrete example in Rust.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust