248 Expert

Kan Extensions

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Kan Extensions" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Kan extensions answer the question: "given functors `F: C -> D` and `G: C -> E`, how do we best extend or lift G along F to get a functor from D to E?" The Right Kan Extension (Ran) and Left Kan Extension (Lan) are the universal solutions to this problem. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Kan extensions answer the question: "given functors F: C -> D and G: C -> E, how do we best extend or lift G along F to get a functor from D to E?" The Right Kan Extension (Ran) and Left Kan Extension (Lan) are the universal solutions to this problem. In functional programming, Ran encodes the Yoneda lemma, and Lan gives rise to coends and existential types. Both appear in the implementation of profunctor optics and indexed traversals.

🎯 Learning Outcomes

• Understand Ran and Lan as universal functorial lifting operations

• Implement Ran as forall b. (a -> f b) -> g b (the right extension)

• Implement Lan as exists b. (f b -> a, g b) (the left extension)

• See how the Yoneda lemma is a special case of Ran

• Compare Kan extensions with OCaml's module-level encoding

Code Example

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

(* Kan extensions: the most general way to extend functors.
   Right Kan extension: Ran K F a = forall b. (a -> K b) -> F b
   Left Kan extension:  Lan K F a = exists b. K b * (F b -> a)
   Every concept in category theory is a Kan extension! *)

(* Right Kan extension (codensity) of the identity functor *)
(* Ran Id F a = forall b. (a -> b) -> F b
   This is the Yoneda lemma! *)

(* Codensity monad: Ran F F
   type 'a codensity = { run : 'b. ('a -> F 'b) -> F 'b } *)
type 'a codensity = { run : 'b. ('a -> 'b list) -> 'b list }

let return_c x = { run = (fun k -> k x) }

let bind_c m f = { run = (fun k -> m.run (fun a -> (f a).run k)) }

(* Lift a list computation *)
let lift_c lst = { run = (fun k -> List.concat_map k lst) }

(* Lower back to list *)
let lower_c c = c.run (fun x -> [x])

let () =
  (* Codensity improves asymptotic complexity of left-nested binds *)
  let program =
    bind_c (lift_c [1; 2; 3]) (fun x ->
    bind_c (lift_c [10; 20])  (fun y ->
    return_c (x + y)))
  in
  let result = lower_c program in
  Printf.printf "codensity: [%s]\n"
    (result |> List.map string_of_int |> String.concat ";");

  (* Verify same as direct computation *)
  let direct = List.concat_map (fun x ->
    List.map (fun y -> x + y) [10; 20]) [1; 2; 3] in
  assert (result = direct);
  Printf.printf "Kan extension (codensity) = direct computation\n"

Key Differences

Aspect	Rust	OCaml
Universal quantification	trait objects (limited)	rank-2 via record fields
Existential (Lan)	`Box<dyn Any>`	GADT existential binding
Codensity monad	explicit Rc wrapping	cleaner with polymorphic functions
Yoneda isomorphism	manual	directly expressible
Kan in practice	Codensity most useful	full generality available

OCaml Approach

OCaml's higher-rank polymorphism makes Ran more direct:

(* Right Kan extension: Ran F G A = { run : 'b. ('a -> 'f 'b) -> 'g 'b } *)
type ('f, 'g, 'a) ran = { run : 'b. ('a -> 'b) -> 'b }  (* Yoneda specialization *)

let to_yoneda : 'a -> ('f, 'g, 'a) ran = fun a -> { run = fun f -> f a }
let from_yoneda : ('f, 'g, 'a) ran -> 'a = fun ran -> ran.run Fun.id

(* Left Kan extension via existential *)
type ('f, 'g, 'a) lan = Lan : ('b -> 'a) * 'b -> ('f, 'g, 'a) lan

OCaml's GADT syntax makes existential types (Lan) particularly clean; Rust needs Box<dyn Any> as a workaround.

Full Source

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

(* Kan extensions: the most general way to extend functors.
   Right Kan extension: Ran K F a = forall b. (a -> K b) -> F b
   Left Kan extension:  Lan K F a = exists b. K b * (F b -> a)
   Every concept in category theory is a Kan extension! *)

(* Right Kan extension (codensity) of the identity functor *)
(* Ran Id F a = forall b. (a -> b) -> F b
   This is the Yoneda lemma! *)

(* Codensity monad: Ran F F
   type 'a codensity = { run : 'b. ('a -> F 'b) -> F 'b } *)
type 'a codensity = { run : 'b. ('a -> 'b list) -> 'b list }

let return_c x = { run = (fun k -> k x) }

let bind_c m f = { run = (fun k -> m.run (fun a -> (f a).run k)) }

(* Lift a list computation *)
let lift_c lst = { run = (fun k -> List.concat_map k lst) }

(* Lower back to list *)
let lower_c c = c.run (fun x -> [x])

let () =
  (* Codensity improves asymptotic complexity of left-nested binds *)
  let program =
    bind_c (lift_c [1; 2; 3]) (fun x ->
    bind_c (lift_c [10; 20])  (fun y ->
    return_c (x + y)))
  in
  let result = lower_c program in
  Printf.printf "codensity: [%s]\n"
    (result |> List.map string_of_int |> String.concat ";");

  (* Verify same as direct computation *)
  let direct = List.concat_map (fun x ->
    List.map (fun y -> x + y) [10; 20]) [1; 2; 3] in
  assert (result = direct);
  Printf.printf "Kan extension (codensity) = direct computation\n"

Deep Comparison

OCaml vs Rust: Kan Extensions

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 toYoneda: F A -> Yoneda F A and fromYoneda: Yoneda F A -> F A for F = Vec and prove they are inverses.

Use Codensity to implement a difference list (O(1) append) and compare performance with a naive list monad on 10,000-element sequences.

Implement the Density comonad (Left Kan extension analog for comonads) and show it gives rise to the Stream comonad.

Show that Ran Id Id A ≅ A by implementing the isomorphism (Yoneda lemma for identity functor).

Implement fromLan: Lan F G A -> G (F^{-1} A) for a concrete invertible functor F (e.g., Newtype).

Open Source Repos

functional-rust

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

Rust