249 Expert

Monad from Adjunction

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Monad from Adjunction" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Every adjunction `F ⊣ G` gives rise to a monad `G ∘ F` with unit `η` and multiplication `G(ε_F)`, and a comonad `F ∘ G` with counit `ε` and comultiplication `F(η_G)`. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Every adjunction F ⊣ G gives rise to a monad G ∘ F with unit η and multiplication G(ε_F), and a comonad F ∘ G with counit ε and comultiplication F(η_G). This is the deepest connection between adjunctions, monads, and comonads. The State monad arises from the product/exponential adjunction; the List monad from the free/forgetful adjunction. This example derives the State monad and its dual the Env comonad from first principles using the product adjunction.

🎯 Learning Outcomes

• Derive the State monad as G ∘ F where F = (- × S) and G = (S → -)

• Implement return as the adjunction unit η and join as G(ε_F)

• Derive the Env comonad as F ∘ G from the same adjunction

• Verify that the monad laws follow from the adjunction coherence conditions

• Compare this systematic derivation with OCaml's more direct categorical encoding

Code Example

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

(* Every adjunction F ⊣ G yields a monad G . F.
   The curry/uncurry adjunction yields the State monad.
   F = (- × S), G = (S → -), G.F = S → (- × S) = State S *)

(* State monad derived from the product-exponential adjunction *)
type ('s, 'a) state = State of ('s -> 'a * 's)

let run (State f) s = f s

(* unit of monad = unit of adjunction *)
let return x = State (fun s -> (x, s))

(* bind = counit . G(eps) where eps is counit of adjunction *)
let bind (State f) k =
  State (fun s ->
    let (a, s') = f s in
    let (State g) = k a in
    g s')

let get       = State (fun s -> (s, s))
let put s     = State (fun _ -> ((), s))
let modify f  = State (fun s -> ((), f s))

let () =
  let program =
    bind get (fun n ->
    bind (put (n + 10)) (fun () ->
    bind get (fun m ->
    bind (modify (fun s -> s * 2)) (fun () ->
    bind get (fun final ->
    return (n, m, final))))))
  in
  let ((a, b, c), s) = run program 5 in
  Printf.printf "initial=%d, after+10=%d, after*2=%d, final_state=%d\n" a b c s;
  Printf.printf "State monad from product-exponential adjunction\n"

Key Differences

Aspect	Rust	OCaml
Adjunction encoding	traits + structs	module signatures
`join` derivation	manual `Box` wrapping	direct function application
Monad laws	require `S: Clone + 'static`	implicit polymorphism
Law verification	runtime tests	qcheck property tests
Generality	product adjunction only	full module parametricity

This derivation demonstrates that State and Env are not ad-hoc constructions but arise necessarily and uniquely from the product adjunction, with no choices involved.

OCaml Approach

OCaml's module system makes the adjunction derivation structurally cleaner:

module type ADJUNCTION = sig
  type s
  (* F A = (A * s), G B = s -> B *)
  val unit   : 'a -> s -> ('a * s)   (* eta *)
  val counit : (s -> 'b) * s -> 'b   (* epsilon *)
end

(* Derived monad: G o F A = s -> (A * s) *)
let return_ a s = (a, s)
let join mma s = let (ma, s') = mma s in ma s'
let bind ma f s = let (a, s') = ma s in f a s'

(* Derived comonad: F o G B = (s -> B) * s *)
let extract (f, s) = f s
let duplicate (f, s) = (fun s' -> (f, s'), s)

Full Source

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

(* Every adjunction F ⊣ G yields a monad G . F.
   The curry/uncurry adjunction yields the State monad.
   F = (- × S), G = (S → -), G.F = S → (- × S) = State S *)

(* State monad derived from the product-exponential adjunction *)
type ('s, 'a) state = State of ('s -> 'a * 's)

let run (State f) s = f s

(* unit of monad = unit of adjunction *)
let return x = State (fun s -> (x, s))

(* bind = counit . G(eps) where eps is counit of adjunction *)
let bind (State f) k =
  State (fun s ->
    let (a, s') = f s in
    let (State g) = k a in
    g s')

let get       = State (fun s -> (s, s))
let put s     = State (fun _ -> ((), s))
let modify f  = State (fun s -> ((), f s))

let () =
  let program =
    bind get (fun n ->
    bind (put (n + 10)) (fun () ->
    bind get (fun m ->
    bind (modify (fun s -> s * 2)) (fun () ->
    bind get (fun final ->
    return (n, m, final))))))
  in
  let ((a, b, c), s) = run program 5 in
  Printf.printf "initial=%d, after+10=%d, after*2=%d, final_state=%d\n" a b c s;
  Printf.printf "State monad from product-exponential adjunction\n"

Deep Comparison

OCaml vs Rust: Monad From Adjunction

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

Derive the Writer<W> monad from the adjunction (- × W) ⊣ (W →) where W is a monoid; implement tell, listen, and pass.

Verify the monad laws for the derived State monad using property tests: left identity, right identity, and associativity.

Derive the Reader<R> monad from the diagonal/product adjunction and implement ask and local.

Implement the monad morphism from State<S, A> to Reader<S, (A, S)> (which is just the function type) and show it respects return and bind.

Show that the unit η and counit ε of the adjunction satisfy the triangle identities computationally by writing tests that check G(ε) ∘ ηG = idG and ε_F ∘ F(η) = idF.

Open Source Repos

functional-rust

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

Rust