🎬 Traits & Generics Shared behaviour, static vs dynamic dispatch, zero-cost polymorphism.

📝 Text version (for readers / accessibility)

• Traits define shared behaviour — like interfaces but with default implementations

• Generics with trait bounds: fn process(item: T) — monomorphized at compile time

• Static dispatch (impl Trait) = zero cost; dynamic dispatch (dyn Trait) = runtime flexibility via vtable

• Blanket implementations apply traits to all types matching a bound

• Associated types and supertraits enable complex type relationships

228: Natural Transformations

Difficulty: 3 Level: Advanced A function that converts one container type to another without touching the values inside.

The Problem This Solves

You often need to switch between container types. A function that might fail returns `Option<T>`, but another API expects `Vec<T>`. Or you want to normalize `Result<T, E>` to `Option<T>` to simplify branching. The naive approach is to write these conversions ad-hoc every time — scattering `match opt { Some(x) => vec![x], None => vec![] }` across your codebase. The problem gets worse when you realize these conversions have a special property worth preserving: they should work the same regardless of what `T` is. A function that converts `Option<i32>` to `Vec<i32>` and a function that converts `Option<String>` to `Vec<String>` should behave identically in structure — the container changes, the contents don't. Without this discipline, you might write conversions that accidentally peek inside the values, or ones that break when you apply a transformation before vs. after the conversion. This leads to subtle bugs in data pipeline code. Natural transformation is the name for this pattern — converting containers in a way that's completely "transparent" to the inner type. This exists to solve exactly that pain.

The Intuition

Think of a container as a "box with a label." `Option<T>` is a box that might be empty or have one item. `Vec<T>` is a box that can have zero or more items. A natural transformation is a rule for relabeling the box — swapping `Option` for `Vec` — without opening the box or touching the items inside. The concrete example: `option_to_vec` converts `None` to `[]` and `Some(x)` to `[x]`. It never looks at what `x` is. You can give it `Option<i32>`, `Option<String>`, `Option<MyStruct>` — the conversion rule is identical. The "natural" part has a precise meaning: it doesn't matter whether you transform the items first and then change the container, or change the container first and then transform the items. Both orders give the same result. In code:

// Convert then map: Some(5) -> [5] -> [10]
option_to_vec(Some(5)).into_iter().map(|x| x * 2).collect::<Vec<_>>()

// Map then convert: Some(5) -> Some(10) -> [10]  
option_to_vec(Some(5).map(|x| x * 2))

// These are always equal — that's what "natural" means

This commutativity guarantee is called the naturality condition, and the code verifies it explicitly.

How It Works in Rust

// A natural transformation: Vec<T> -> Option<T>
// Takes the first element (or None if empty)
// Notice: fn<T> — works for ANY T without any bounds
pub fn safe_head<T: Clone>(list: &[T]) -> Option<T> {
 list.first().cloned()
}

// The reverse transformation: Option<T> -> Vec<T>
pub fn option_to_vec<T>(opt: Option<T>) -> Vec<T> {
 match opt {
     None => vec![],          // empty container -> empty container
     Some(x) => vec![x],     // one item -> one-element list
 }
}

// Verify the naturality condition for any nat transform
// "nat_t" and "nat_u" are the same function, just instantiated at different types
// (Rust monomorphizes — one generic fn becomes multiple concrete fns at compile time)
pub fn verify_naturality<T, U>(
 f: impl Fn(T) -> U,          // the function to apply to values
 nat_t: impl Fn(&[T]) -> Option<T>,  // nat transform at type T
 nat_u: impl Fn(&[U]) -> Option<U>,  // nat transform at type 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);        // transform values, then change container
 let rhs = nat_t(list).map(f);    // change container, then transform values
 lhs == rhs                        // must be equal!
}

// Natural transformations compose — chain two container changes
pub fn nat_composed<T: Clone>(list: &[T]) -> Vec<T> {
 option_to_vec(safe_head(list))   // Vec -> Option -> Vec
}

The `verify_naturality` function needs two parameters for the same generic function because Rust monomorphizes generics — there's no way to pass "the same generic function twice" as a single value. This is a known limitation vs. OCaml.

What This Unlocks

Data pipeline normalization: Consistently convert between `Option`, `Result`, `Vec` at API boundaries without ad-hoc match expressions scattered everywhere.
Container adapters: Build composable adapters (`result_to_opt`, `opt_to_vec`, etc.) that can be chained predictably because they're all natural transformations.
Iterator combinators: `Iterator::flatten`, `Option::into_iter`, `Result::ok` are all natural transformations — understanding this explains why they compose so cleanly.

Key Differences

Concept	OCaml	Rust
Polymorphic function	`'a list -> 'a option` intrinsically polymorphic	Generic `fn<T>`, monomorphized per use
Passing nat transforms as values	Single polymorphic function value	Need two monomorphized copies (`nat_t` and `nat_u`)
Naturality verification	Works with one polymorphic `nat` argument	Requires `nat_t: fn(&[T])->Option<T>` and `nat_u: fn(&[U])->Option<U>`
Naturality by construction	Parametric polymorphism guarantees it	Same — any `fn<T>(Vec<T>) -> Option<T>` that ignores `T` is automatically natural
Ownership	References, GC-managed	`Clone` required to return owned values

/// 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).
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)`
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
}

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

fn main() {
    // Basic natural transformations
    println!("safe_head([1,2,3])    = {:?}", safe_head(&[1, 2, 3]));
    println!("safe_head([])         = {:?}", safe_head::<i32>(&[]));
    println!("safe_head_recursive([1,2,3]) = {:?}", safe_head_recursive(&[1, 2, 3]));
    println!("safe_last([1,2,3])    = {:?}", safe_last(&[1, 2, 3]));
    println!("safe_last([])         = {:?}", safe_last::<i32>(&[]));

    println!();

    // option_to_vec: Option → Vec
    println!("option_to_vec(Some(42)) = {:?}", option_to_vec(Some(42)));
    println!("option_to_vec(None)     = {:?}", option_to_vec::<i32>(None));

    println!();

    // Verify naturality: safe_head is a natural transformation w.r.t. i32 -> String
    let lists: &[&[i32]] = &[&[], &[1], &[1, 2, 3], &[42, 0, -1]];
    let all_natural = lists
        .iter()
        .all(|lst| verify_naturality(|x: i32| x.to_string(), safe_head, safe_head, lst));
    println!("safe_head is natural (int->string)? {all_natural}");

    println!();

    // Composition of natural transformations
    println!(
        "nat_composed([1,2,3]) = {:?}",
        nat_composed(&[1, 2, 3])
    );
    println!("nat_composed([])      = {:?}", nat_composed::<i32>(&[]));
}

/* Output:
   safe_head([1,2,3])    = Some(1)
   safe_head([])         = None
   safe_head_recursive([1,2,3]) = Some(1)
   safe_last([1,2,3])    = Some(3)
   safe_last([])         = None

   option_to_vec(Some(42)) = [42]
   option_to_vec(None)     = []

   safe_head is natural (int->string)? true

   nat_composed([1,2,3]) = [1]
   nat_composed([])      = []
*/

#[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 ";")

📊 Detailed Comparison

OCaml vs Rust: Natural Transformations

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

(* 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

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.