228 Advanced

Natural Transformations

Category Theory

Tutorial Video

Text description (accessibility)

This video demonstrates the "Natural Transformations" functional Rust example. Difficulty level: Advanced. Key concepts covered: Category Theory. Implement and verify natural transformations between functors — structure-preserving maps that commute with `fmap`. Key difference from OCaml: 1. **Polymorphism:** OCaml's `'a list

Tutorial

The Problem

Implement and verify natural transformations between functors — structure-preserving maps that commute with fmap. Demonstrate the naturality condition, horizontal composition, and the relationship between List and Option functors.

🎯 Learning Outcomes

• What a natural transformation is in programming terms: a polymorphic function F<A> → G<A>

• How to verify the naturality square: nat(fmap f xs) == fmap f (nat xs)

• How natural transformations compose to form the functor category

• How Rust's generic functions encode parametric naturality by construction

🦀 The Rust Way

Rust uses generic functions bounded by Clone and PartialEq to implement nat transformations. Because Rust lacks polymorphic function values (no rank-2 types), verify_naturality takes two monomorphized copies of the nat transformation — one for each type — which the compiler instantiates automatically from the same generic function. Composition is a simple function call chain.

Code Example

pub fn safe_head<T: Clone>(list: &[T]) -> Option<T> {
    list.first().cloned()
}

pub fn verify_naturality<T, U>(
    f: impl Fn(T) -> U,
    nat_t: impl Fn(&[T]) -> Option<T>,
    nat_u: impl Fn(&[U]) -> Option<U>,
    list: &[T],
) -> bool
where
    T: Clone,
    U: PartialEq,
{
    let mapped: Vec<U> = list.iter().map(|x| f(x.clone())).collect();
    let lhs = nat_u(&mapped);
    let rhs = nat_t(list).map(f);
    lhs == rhs
}

(* Safe head: list -> option (natural transformation) *)
let safe_head lst = match lst with [] -> None | x :: _ -> Some x

(* Verify naturality: nat(fmap f xs) == fmap f (nat xs) *)
let verify_naturality f nat lst =
  let lhs = nat (List.map f lst) in
  let rhs = Option.map f (nat lst) in
  lhs = rhs

(* Composition: list -[safe_head]-> option -[option_to_list]-> list *)
let option_to_list o = match o with None -> [] | Some x -> [x]
let nat_composed lst = option_to_list (safe_head lst)

Key Differences

Polymorphism: OCaml's 'a list -> 'a option is intrinsically polymorphic; Rust

monomorphizes each use, so verify_naturality needs nat_t and nat_u separately.

Ownership: Rust returns owned T (via .cloned()) rather than references, keeping

the API simple at the cost of requiring T: Clone.

Naturality by construction: Rust's parametric generics guarantee naturality for free

— any fn<T>(Vec<T>) -> Option<T> that doesn't inspect T is automatically natural.

Composition: OCaml uses function application; Rust is identical — option_to_vec(safe_head(list)) chains two nat transformations directly.

OCaml Approach

OCaml expresses natural transformations as polymorphic functions. The naturality condition is verified with List.map and Option.map. Higher-order functions accept both the morphism f and the nat transformation nat, checking both sides of the commutative square. The structural equality = makes the check concise.

Full Source

#![allow(clippy::all)]
//! Natural Transformations: structure-preserving maps between functors.
//!
//! A natural transformation η: F → G between functors F, G: C → D
//! assigns to each object A in C a morphism η_A: F(A) → G(A),
//! such that for every morphism f: A → B in C, the naturality square commutes:
//!   G(f) ∘ η_A = η_B ∘ F(f)
//!
//! In programming terms: `nat(fmap f xs) == fmap f (nat xs)`

/// Safe head: `&[T]` → `Option<T>` (a natural transformation from List to Option).
///
/// Idiomatic Rust: delegate to `slice::first()` and clone the element.
pub fn safe_head<T: Clone>(list: &[T]) -> Option<T> {
    list.first().cloned()
}

/// Safe head — recursive, OCaml-style pattern matching.
pub fn safe_head_recursive<T: Clone>(list: &[T]) -> Option<T> {
    match list {
        [] => None,
        [x, ..] => Some(x.clone()),
    }
}

/// Safe last: `&[T]` → `Option<T>` (another natural transformation from List to Option).
pub fn safe_last<T: Clone>(list: &[T]) -> Option<T> {
    list.last().cloned()
}

/// `Option<T>` → `Vec<T>` (natural transformation: singleton list or empty list).
///
/// This is the unit of the List monad restricted to Option.
pub fn option_to_vec<T>(opt: Option<T>) -> Vec<T> {
    match opt {
        None => vec![],
        Some(x) => vec![x],
    }
}

/// Verify the naturality condition for a natural transformation `nat: &[T] → Option<T>`.
///
/// The naturality square commutes iff:
///   `nat_u(list.map(f)) == nat_t(list).map(f)`
///
/// Both `nat_t` and `nat_u` must be the same natural transformation,
/// instantiated at types `T` and `U` respectively.
pub fn verify_naturality<T, U>(
    f: impl Fn(T) -> U,
    nat_t: impl Fn(&[T]) -> Option<T>,
    nat_u: impl Fn(&[U]) -> Option<U>,
    list: &[T],
) -> bool
where
    T: Clone,
    U: PartialEq,
{
    // LHS: map f over the list first, then apply the nat transformation
    let mapped: Vec<U> = list.iter().map(|x| f(x.clone())).collect();
    let lhs = nat_u(&mapped);
    // RHS: apply the nat transformation first, then map f over the result
    // `f` is moved here after the shared borrow in the closure above was released
    let rhs = nat_t(list).map(f);
    lhs == rhs
}

/// Composed natural transformation: `&[T]` → `Vec<T>`
/// via `&[T]` -[safe_head]→ `Option<T>` -[option_to_vec]→ `Vec<T>`.
///
/// Demonstrates that natural transformations compose to yield another natural transformation.
pub fn nat_composed<T: Clone>(list: &[T]) -> Vec<T> {
    option_to_vec(safe_head(list))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_safe_head_empty() {
        assert_eq!(safe_head::<i32>(&[]), None);
    }

    #[test]
    fn test_safe_head_single() {
        assert_eq!(safe_head(&[42]), Some(42));
    }

    #[test]
    fn test_safe_head_multiple() {
        assert_eq!(safe_head(&[1, 2, 3]), Some(1));
    }

    #[test]
    fn test_safe_head_recursive_agrees_with_idiomatic() {
        let cases: &[&[i32]] = &[&[], &[7], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert_eq!(safe_head(list), safe_head_recursive(list));
        }
    }

    #[test]
    fn test_safe_last_empty() {
        assert_eq!(safe_last::<i32>(&[]), None);
    }

    #[test]
    fn test_safe_last_single() {
        assert_eq!(safe_last(&[99]), Some(99));
    }

    #[test]
    fn test_safe_last_multiple() {
        assert_eq!(safe_last(&[1, 2, 3]), Some(3));
    }

    #[test]
    fn test_option_to_vec_none() {
        assert_eq!(option_to_vec::<i32>(None), vec![]);
    }

    #[test]
    fn test_option_to_vec_some() {
        assert_eq!(option_to_vec(Some(5)), vec![5]);
    }

    #[test]
    fn test_naturality_safe_head_int_to_string() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert!(
                verify_naturality(|x: i32| x.to_string(), safe_head, safe_head, list),
                "naturality failed for {list:?}"
            );
        }
    }

    #[test]
    fn test_naturality_safe_last_int_to_int() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert!(
                verify_naturality(|x: i32| x * 2, safe_last, safe_last, list),
                "naturality failed for {list:?}"
            );
        }
    }

    #[test]
    fn test_nat_composed_nonempty() {
        assert_eq!(nat_composed(&[1, 2, 3]), vec![1]);
    }

    #[test]
    fn test_nat_composed_empty() {
        assert_eq!(nat_composed::<i32>(&[]), vec![]);
    }

    #[test]
    fn test_nat_composed_single() {
        assert_eq!(nat_composed(&[42]), vec![42]);
    }
}

(* Natural transformations: morphisms in the functor category.
   Key property: commutes with fmap — "structure preserving" *)

(* Safe head: list -> option (natural transformation) *)
let safe_head lst = match lst with [] -> None | x :: _ -> Some x

(* Safe last *)
let safe_last lst = match List.rev lst with [] -> None | x :: _ -> Some x

(* Horizontal composition: nat trans can be composed *)
let reverse_opt : 'a option -> 'a option = fun x -> x  (* identity on option *)

(* Naturality square verification *)
let verify_naturality f nat lst =
  let lhs = nat (List.map f lst) in  (* map then transform *)
  let rhs = Option.map f (nat lst) in  (* transform then map *)
  lhs = rhs

let () =
  (* Verify safe_head is natural w.r.t. string_of_int *)
  let lists = [[] ; [1]; [1;2;3]; [42;0;-1]] in
  let natural = List.for_all (verify_naturality string_of_int safe_head) lists in
  Printf.printf "safe_head natural? %b\n" natural;

  (* Composition of natural transformations *)
  (* list -[safe_head]-> option -[option_to_list]-> list *)
  let option_to_list o = match o with None -> [] | Some x -> [x] in
  let nat_composed lst = option_to_list (safe_head lst) in

  Printf.printf "composed [1;2;3]: [%s]\n"
    (nat_composed [1;2;3] |> List.map string_of_int |> String.concat ";");
  Printf.printf "composed []: [%s]\n"
    (nat_composed [] |> List.map string_of_int |> String.concat ";")

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_safe_head_empty() {
        assert_eq!(safe_head::<i32>(&[]), None);
    }

    #[test]
    fn test_safe_head_single() {
        assert_eq!(safe_head(&[42]), Some(42));
    }

    #[test]
    fn test_safe_head_multiple() {
        assert_eq!(safe_head(&[1, 2, 3]), Some(1));
    }

    #[test]
    fn test_safe_head_recursive_agrees_with_idiomatic() {
        let cases: &[&[i32]] = &[&[], &[7], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert_eq!(safe_head(list), safe_head_recursive(list));
        }
    }

    #[test]
    fn test_safe_last_empty() {
        assert_eq!(safe_last::<i32>(&[]), None);
    }

    #[test]
    fn test_safe_last_single() {
        assert_eq!(safe_last(&[99]), Some(99));
    }

    #[test]
    fn test_safe_last_multiple() {
        assert_eq!(safe_last(&[1, 2, 3]), Some(3));
    }

    #[test]
    fn test_option_to_vec_none() {
        assert_eq!(option_to_vec::<i32>(None), vec![]);
    }

    #[test]
    fn test_option_to_vec_some() {
        assert_eq!(option_to_vec(Some(5)), vec![5]);
    }

    #[test]
    fn test_naturality_safe_head_int_to_string() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert!(
                verify_naturality(|x: i32| x.to_string(), safe_head, safe_head, list),
                "naturality failed for {list:?}"
            );
        }
    }

    #[test]
    fn test_naturality_safe_last_int_to_int() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3], &[42, 0, -1]];
        for list in cases {
            assert!(
                verify_naturality(|x: i32| x * 2, safe_last, safe_last, list),
                "naturality failed for {list:?}"
            );
        }
    }

    #[test]
    fn test_nat_composed_nonempty() {
        assert_eq!(nat_composed(&[1, 2, 3]), vec![1]);
    }

    #[test]
    fn test_nat_composed_empty() {
        assert_eq!(nat_composed::<i32>(&[]), vec![]);
    }

    #[test]
    fn test_nat_composed_single() {
        assert_eq!(nat_composed(&[42]), vec![42]);
    }
}

Deep Comparison

OCaml vs Rust: Natural Transformations

Side-by-Side Code

OCaml

(* Safe head: list -> option (natural transformation) *)
let safe_head lst = match lst with [] -> None | x :: _ -> Some x

(* Verify naturality: nat(fmap f xs) == fmap f (nat xs) *)
let verify_naturality f nat lst =
  let lhs = nat (List.map f lst) in
  let rhs = Option.map f (nat lst) in
  lhs = rhs

(* Composition: list -[safe_head]-> option -[option_to_list]-> list *)
let option_to_list o = match o with None -> [] | Some x -> [x]
let nat_composed lst = option_to_list (safe_head lst)

Rust (idiomatic)

pub fn safe_head<T: Clone>(list: &[T]) -> Option<T> {
    list.first().cloned()
}

pub fn verify_naturality<T, U>(
    f: impl Fn(T) -> U,
    nat_t: impl Fn(&[T]) -> Option<T>,
    nat_u: impl Fn(&[U]) -> Option<U>,
    list: &[T],
) -> bool
where
    T: Clone,
    U: PartialEq,
{
    let mapped: Vec<U> = list.iter().map(|x| f(x.clone())).collect();
    let lhs = nat_u(&mapped);
    let rhs = nat_t(list).map(f);
    lhs == rhs
}

Rust (functional/recursive)

pub fn safe_head_recursive<T: Clone>(list: &[T]) -> Option<T> {
    match list {
        [] => None,
        [x, ..] => Some(x.clone()),
    }
}

pub fn option_to_vec<T>(opt: Option<T>) -> Vec<T> {
    match opt {
        None => vec![],
        Some(x) => vec![x],
    }
}

pub fn nat_composed<T: Clone>(list: &[T]) -> Vec<T> {
    option_to_vec(safe_head(list))
}

Type Signatures

Concept	OCaml	Rust
Safe head	`val safe_head : 'a list -> 'a option`	`fn safe_head<T: Clone>(list: &[T]) -> Option<T>`
Option to list	`val option_to_list : 'a option -> 'a list`	`fn option_to_vec<T>(opt: Option<T>) -> Vec<T>`
Naturality verifier	`('a -> 'b) -> ('a list -> 'a option) -> 'a list -> bool`	`(T→U, Fn(&[T])→Option<T>, Fn(&[U])→Option<U>, &[T]) → bool`
Composed nat trans	`'a list -> 'a list`	`fn nat_composed<T: Clone>(list: &[T]) -> Vec<T>`

Key Insights

Parametric naturality: In both languages, a polymorphic function that treats its

type parameter uniformly (no Typeable/Any tricks) is automatically natural. Rust's generics enforce this structurally.

Rank-2 types: OCaml accepts a single polymorphic nat argument. Rust requires two

monomorphized copies (nat_t and nat_u), since Rust has no rank-2 type polymorphism. The compiler instantiates the same generic function at both types at call sites.

Ownership and cloning: OCaml's garbage collector shares values freely. Rust's

T: Clone bound makes the copy cost explicit — .cloned() on slices allocates owned values so we can return them without dangling references.

The naturality square: The commuting condition nat(fmap f xs) == fmap f (nat xs)

means applying the morphism before or after the nat transformation yields the same result. This is what makes a nat transformation "structure preserving" across the functor category.

Composition: Natural transformations compose component-wise. option_to_vec ∘ safe_head

yields another valid nat transformation [T] → Vec<T>, which is exactly nat_composed. The type system ensures the composition is well-formed.

When to Use Each Style

Use idiomatic Rust when: Calling library methods like .first(), .last(), or .cloned() on slices — they compose cleanly and communicate intent directly.

Use recursive Rust when: Teaching the OCaml parallel explicitly, or when the structural decomposition of the input (empty vs. cons) is the central learning point.

Exercises

Implement a natural transformation from Result<T, E> to Option<T> that discards the error, and verify the naturality square holds for a sample function f: T -> U.

Write a natural transformation from Vec<T> to Option<T> that returns the first element (head), and implement its inverse as a partial natural transformation.

Define a Monad trait (with unit and bind) for Option, implement it, then use natural transformations to lift a computation from Vec context into Option context.

Open Source Repos

functional-rust

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

Rust