246 Expert

Adjunctions

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Adjunctions" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. An adjunction between two functors `F` and `G` is a natural bijection between morphisms: `Hom(F A, B) ≅ Hom(A, G B)`. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

An adjunction between two functors F and G is a natural bijection between morphisms: Hom(F A, B) ≅ Hom(A, G B). Adjunctions are the categorical generalization of "best approximations" and appear everywhere in functional programming: currying is an adjunction, the product/exponent adjunction underlies closures, and many monad/comonad pairs arise from adjunctions. This example implements adjunctions in Rust and shows how the State and Env comonad/monad pair emerges from the product adjunction.

🎯 Learning Outcomes

• Understand adjunctions via the unit and counit natural transformations

• Implement the product/diagonal adjunction giving rise to Reader/Writer

• Derive a monad from the composition G ∘ F using adjunction data

• Derive a comonad from the composition F ∘ G using adjunction data

• Compare Rust's trait-encoded adjunctions with OCaml's module functors

Code Example

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

(* Adjunction: F ⊣ G means Hom(F A, B) ≅ Hom(A, G B)
   Classic example: (- × C) ⊣ (C → -)
   i.e., curry/uncurry is an adjunction *)

(* The curry/uncurry adjunction *)
let curry   f a b = f (a, b)
let uncurry f (a, b) = f a b

(* unit of the adjunction: a -> C -> (A × C) *)
let unit c a = (a, c)

(* counit: (A × C → B) × (A × C) → B *)
let counit f pair = f pair

(* Verify the adjunction: curry . uncurry = id, uncurry . curry = id *)
let () =
  let f (a, b) = a + b in
  let g a b = a * b in

  let f' = curry (uncurry f) in
  assert (f' 3 4 = f (3, 4));

  let g' = uncurry (curry g) in
  assert (g' (3, 4) = g 3 4);

  Printf.printf "curry . uncurry = id: %b\n" (f' 3 4 = f (3, 4));
  Printf.printf "uncurry . curry = id: %b\n" (g' (3, 4) = g 3 4);

  (* The product-exponential adjunction *)
  (* Hom(A × B, C) ≅ Hom(A, B → C) *)
  let add_curried = curry (fun (a, b) -> a + b) in
  Printf.printf "curried add 3 4 = %d\n" (add_curried 3 4);
  let add_uncurried = uncurry (fun a b -> a + b) in
  Printf.printf "uncurried add (3,4) = %d\n" (add_uncurried (3, 4))

Key Differences

Aspect	Rust	OCaml
Functor encoding	trait + struct	module type + module
Type families	associated types	module type parameters
Adjunction laws	runtime tests	module coherence
Higher-kinded	simulated via GATs	module polymorphism
Monad derivation	manual `bind`	can derive via functor composition

Adjunctions provide a systematic way to derive monads and comonads: every adjunction gives rise to a monad G ∘ F and a comonad F ∘ G.

OCaml Approach

OCaml uses functors (module-level) for adjunctions:

module type ADJUNCTION = sig
  type 'a left_f   (* F A *)
  type 'a right_g  (* G B *)
  val unit   : 'a -> 'a left_f right_g
  val counit : 'a right_g left_f -> 'a
end

(* Product adjunction: F = (E *), G = (E ->) *)
module ProdAdj (E : sig type t val e : t end) = struct
  type 'a left_f  = E.t * 'a
  type 'a right_g = E.t -> 'a
  let unit a e = (e, a)
  let counit (e, f) = f e
end

OCaml functors map cleanly to categorical functors; Rust traits simulate the same with more verbosity.

Full Source

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

(* Adjunction: F ⊣ G means Hom(F A, B) ≅ Hom(A, G B)
   Classic example: (- × C) ⊣ (C → -)
   i.e., curry/uncurry is an adjunction *)

(* The curry/uncurry adjunction *)
let curry   f a b = f (a, b)
let uncurry f (a, b) = f a b

(* unit of the adjunction: a -> C -> (A × C) *)
let unit c a = (a, c)

(* counit: (A × C → B) × (A × C) → B *)
let counit f pair = f pair

(* Verify the adjunction: curry . uncurry = id, uncurry . curry = id *)
let () =
  let f (a, b) = a + b in
  let g a b = a * b in

  let f' = curry (uncurry f) in
  assert (f' 3 4 = f (3, 4));

  let g' = uncurry (curry g) in
  assert (g' (3, 4) = g 3 4);

  Printf.printf "curry . uncurry = id: %b\n" (f' 3 4 = f (3, 4));
  Printf.printf "uncurry . curry = id: %b\n" (g' (3, 4) = g 3 4);

  (* The product-exponential adjunction *)
  (* Hom(A × B, C) ≅ Hom(A, B → C) *)
  let add_curried = curry (fun (a, b) -> a + b) in
  Printf.printf "curried add 3 4 = %d\n" (add_curried 3 4);
  let add_uncurried = uncurry (fun a b -> a + b) in
  Printf.printf "uncurried add (3,4) = %d\n" (add_uncurried (3, 4))

Deep Comparison

OCaml vs Rust: Adjunctions

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 the diagonal adjunction Δ ⊣ × (diagonal functor left adjoint to product), which gives rise to the tuple monad.

Verify both triangle identities programmatically: G(ε) ∘ η_G = id_G and ε_F ∘ F(η) = id_F.

Derive the Writer<W, A> monad from the adjunction between (- × W) and (W →) where W is a monoid.

Show that the List monad arises from the free/forgetful adjunction between Set and Mon (monoids).

Implement the adjoint transpose: given f: F A -> B, produce f̂: A -> G B using unit and fmap.

Open Source Repos

functional-rust

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

Rust