235 Expert

Yoneda Lemma

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Yoneda Lemma" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The Yoneda lemma is one of the most important results in category theory: `Nat(Hom(A, -), F) ≅ F(A)`. Key difference from OCaml: 1. **Rank

Tutorial

The Problem

The Yoneda lemma is one of the most important results in category theory: Nat(Hom(A, -), F) ≅ F(A). In Rust terms: a natural transformation from fn(A, -) to any functor F is in one-to-one correspondence with a value of F(A). The practical consequence: Yoneda<F, A> — a type holding a natural transformation — is isomorphic to F(A> but enables free map operations without actually running them, accumulating a composition chain that is applied all at once.

🎯 Learning Outcomes

• Understand the Yoneda lemma as a correspondence between natural transformations and functor values

• Learn how Yoneda<F, A> defers and fuses map operations (Yoneda's performance benefit)

• See the proof: to_yoneda(fa)(id) = fa and from_yoneda(y) = y(id)

• Connect to free Functor instances: any type with a Yoneda wrapper gets map for free

Code Example

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

(* Yoneda lemma: Nat(Hom(A,-), F) ≅ F(A)
   In Haskell/OCaml: (forall b. (a -> b) -> f b) ≅ f a
   The "free theorem" that justifies many optimizations. *)

(* The Yoneda embedding *)
type ('a, 'f) yoneda = { run : 'b. ('a -> 'b) -> 'f }

(* Yoneda for list functor *)
type 'a yoneda_list = { run_list : 'b. ('a -> 'b) -> 'b list }

(* Convert list to yoneda *)
let to_yoneda : 'a list -> 'a yoneda_list =
  fun lst -> { run_list = (fun f -> List.map f lst) }

(* Convert yoneda back to list *)
let from_yoneda : 'a yoneda_list -> 'a list =
  fun y -> y.run_list (fun x -> x)  (* use identity *)

(* fmap for free! — no actual mapping happens until runYoneda *)
let fmap_yoneda f y =
  { run_list = (fun g -> y.run_list (fun a -> g (f a)) ) }

let () =
  let lst = [1; 2; 3; 4; 5] in
  let y = to_yoneda lst in

  (* Fuse multiple maps — only traverses once! *)
  let y' = fmap_yoneda (fun x -> x + 1) (fmap_yoneda (fun x -> x * 2) y) in
  let result = from_yoneda y' in
  Printf.printf "Yoneda fused maps: [%s]\n"
    (result |> List.map string_of_int |> String.concat ";");

  (* Same result as direct maps *)
  let direct = List.map (fun x -> x * 2 + 1) lst in
  assert (result = direct);
  Printf.printf "Yoneda ≅ direct: same result\n"

Key Differences

Rank-2 types: OCaml's 'b. record polymorphism expresses Yoneda directly; Rust requires defunctionalization (GAT markers).

Performance benefit: Both languages benefit from Yoneda map fusion; Haskell's library uses it for stream fusion; Rust's iterator fusion is an analogous (compiler-level) optimization.

Free Functor: Yoneda provides a free Functor instance for any type constructor — even non-functors can be mapped over via Yoneda lifting.

Practical use: Yoneda is primarily educational; the performance benefit is achieved automatically by LLVM in Rust for iterator chains.

OCaml Approach

OCaml's Yoneda:

type ('f, 'a) yoneda = { run : 'b. ('a -> 'b) -> 'b 'f }
let to_yoneda fa = { run = fun f -> map f fa }
let from_yoneda y = y.run Fun.id
let map_yoneda f y = { run = fun g -> y.run (g >> f) }

map_yoneda fuses the function f into the natural transformation without actually running it. OCaml's rank-2 type 'b. enables the polymorphic run field.

Full Source

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

(* Yoneda lemma: Nat(Hom(A,-), F) ≅ F(A)
   In Haskell/OCaml: (forall b. (a -> b) -> f b) ≅ f a
   The "free theorem" that justifies many optimizations. *)

(* The Yoneda embedding *)
type ('a, 'f) yoneda = { run : 'b. ('a -> 'b) -> 'f }

(* Yoneda for list functor *)
type 'a yoneda_list = { run_list : 'b. ('a -> 'b) -> 'b list }

(* Convert list to yoneda *)
let to_yoneda : 'a list -> 'a yoneda_list =
  fun lst -> { run_list = (fun f -> List.map f lst) }

(* Convert yoneda back to list *)
let from_yoneda : 'a yoneda_list -> 'a list =
  fun y -> y.run_list (fun x -> x)  (* use identity *)

(* fmap for free! — no actual mapping happens until runYoneda *)
let fmap_yoneda f y =
  { run_list = (fun g -> y.run_list (fun a -> g (f a)) ) }

let () =
  let lst = [1; 2; 3; 4; 5] in
  let y = to_yoneda lst in

  (* Fuse multiple maps — only traverses once! *)
  let y' = fmap_yoneda (fun x -> x + 1) (fmap_yoneda (fun x -> x * 2) y) in
  let result = from_yoneda y' in
  Printf.printf "Yoneda fused maps: [%s]\n"
    (result |> List.map string_of_int |> String.concat ";");

  (* Same result as direct maps *)
  let direct = List.map (fun x -> x * 2 + 1) lst in
  assert (result = direct);
  Printf.printf "Yoneda ≅ direct: same result\n"

Deep Comparison

OCaml vs Rust: Yoneda Lemma

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 to_yoneda and from_yoneda for Option<A> and verify the round-trip: from_yoneda(to_yoneda(fa)) == fa.

Demonstrate map fusion: apply 10 map operations via Yoneda and verify only one actual traversal occurs.

Prove the Yoneda isomorphism: to_yoneda(from_yoneda(y)) == y for a specific y.

Open Source Repos

functional-rust

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

Rust