🎬 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

227: Functor Category — Natural Transformations

Difficulty: ⭐⭐⭐ Level: Advanced How to convert between container types (e.g., `Vec` → `Option`) in a way that's guaranteed to be consistent with mapping.

The Problem This Solves

You have a `Vec<i32>` and you want to grab its first element as an `Option<i32>`. Simple:

let first = vec.first().copied();

But here's the subtle question: does it matter whether you map before or after converting? In other words, are these the same?

// Option A: convert, then map
let a = vec.first().copied().map(|x| x * 2);

// Option B: map, then convert
let b = vec.iter().copied().map(|x| x * 2).next();  // approximately

If they give different answers, your conversion function is hiding behavior — transforming data as a side effect of converting the container type. That's a bug waiting to happen. A natural transformation is a conversion between container types (like `Vec → Option`) that is provably consistent with mapping — no matter what function you map, no matter what order you do it in, you get the same result. The condition "map-then-convert equals convert-then-map" is called the naturality condition, and it's a mathematical guarantee that your conversion function is honest: it only changes the container shape, never the values inside. This concept exists to give you a precise tool for reasoning about container conversions in generic code, and to catch conversion functions that secretly transform data.

The Intuition

Imagine translating a book from English to Spanish. If the translation is faithful (a "natural transformation"), then:

Translating the book, then reading chapter 1 = reading chapter 1, then translating that chapter

The order shouldn't matter. If the Spanish version of chapter 1 is different depending on when you extracted it, your translator is not being faithful — they're adding or changing content. In code: converting `Vec<T>` to `Option<T>` (by taking the first element) is a "faithful" conversion if:

map(f) over Vec, then take first  ===  take first, then map(f) over Option

The naturality condition is exactly this commutativity: applying `f` before or after the conversion gives the same result. Functions that satisfy this are called natural transformations — they convert between container shapes without touching the values. You don't need to know category theory to use this concept. The practical takeaway: if your container conversion passes the naturality check, it's safe to use in generic code because you can freely reorder map and conversion.

How It Works in Rust

Step 1 — A natural transformation: Vec → Option (take first element)

// "Natural transformation" sounds fancy; it's just a generic function
// that converts one container type to another
pub fn list_to_option<T>(list: &[T]) -> Option<&T> {
 list.first()  // None if empty, Some(&first_element) if not
}

Step 2 — Another natural transformation: Option → Vec

pub fn option_to_list<T>(opt: Option<T>) -> Vec<T> {
 match opt {
     None    => vec![],    // empty container → empty list
     Some(x) => vec![x],  // single element → single-element list
 }
}

Step 3 — Verify the naturality condition This is the key: does mapping before or after the conversion give the same result?

pub fn naturality_holds<T, U, F>(list: &[T], f: F) -> bool
where
 T: Clone,
 U: PartialEq,
 F: Fn(T) -> U,
{
 // Option A: map f over the Vec, then take first
 let mapped: Vec<U> = list.iter().cloned().map(&f).collect();
 let lhs = mapped.first();

 // Option B: take first from Vec, then map f over the Option
 let rhs = list.first().cloned().map(f);

 lhs == rhs.as_ref()  // must be equal for naturality to hold
}

Testing it:

// Works for any f and any list — naturality holds for list_to_option
assert!(naturality_holds(&[1i32, 2, 3], |x| x * 2));  // true
assert!(naturality_holds::<i32, i32, _>(&[], |x| x * 2));  // true (both None)

Step 4 — Alternative style using pattern matching:

pub fn list_to_option_rec<T>(list: &[T]) -> Option<&T> {
 match list {
     []          => None,
     [head, ..]  => Some(head),
 }
}

Both implementations produce the same results — and both satisfy naturality. The naturality condition is about the semantic contract, not the implementation. What would break naturality? A "conversion" that secretly modifies the value:

// BAD — not a natural transformation because it transforms the data!
fn bad_list_to_option(list: &[i32]) -> Option<i32> {
 list.first().map(|x| x * 2)  // secretly doubles the first element
}
// naturality_holds fails: map(*2) then convert ≠ convert then map(*2)

What This Unlocks

Safely reorder map and conversion in generic code. If your `F<T> → G<T>` function satisfies naturality, you can freely push maps past container conversions without changing semantics. Generic algorithms can assume this and simplify code.
A vocabulary for container interop. When you write `vec.first()`, `option.into_iter()`, `result.ok()` — these are all natural transformations. Now you know why they're safe: they preserve the naturality condition.
Testing infrastructure for container APIs. The `naturality_holds` function is a reusable property test. Plug in any container conversion and any function — if it holds for many random inputs (using `proptest`), your conversion is trustworthy.

Real codebases where this pattern appears: the `Iterator` trait's `from_iter`/`into_iter` conversions, `Option`/`Result` interop (`option.ok_or(err)`, `result.ok()`), async runtime combinators that convert between `Future` and `Stream` types, and parser combinators that convert between different parse result types.

Key Differences

Concept	OCaml	Rust
Functor interface	`module type FUNCTOR` with `type 'a t` and `val map`	No direct equivalent — Rust lacks higher-kinded types
Natural transformation type	`'a ListF.t -> 'a OptionF.t` (implicit polymorphism)	`fn<T>(list: &[T]) -> Option<&T>` (explicit generic `T`)
Higher-kinded types	Native — `'a list`, `'a option` as type constructors	Not available — must use concrete types or workarounds
Naturality verification	`assert` inline at runtime	Generic function `naturality_holds<T,U,F>` with trait bounds
Borrow vs copy	OCaml returns new values (GC-managed)	Returns `Option<&T>` — a borrow, zero allocation
Polymorphism	Implicit via `'a` type variables	Explicit `<T>` generic parameters
`list.first()` equivalent	`List.nth_opt lst 0` or pattern match	`slice.first()` → `Option<&T>`

// Natural transformation: Vec → Option (take the head element)
pub fn list_to_option<T>(list: &[T]) -> Option<&T> {
    list.first()
}

// Natural transformation: Vec → Option (functional/recursive style)
pub fn list_to_option_rec<T>(list: &[T]) -> Option<&T> {
    match list {
        [] => None,
        [head, ..] => Some(head),
    }
}

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

// Verify the naturality condition for `list_to_option`:
//   list_to_option(map f lst)  ==  map f (list_to_option lst)
pub fn naturality_holds<T, U, F>(list: &[T], f: F) -> bool
where
    T: Clone,
    U: PartialEq,
    F: Fn(T) -> U,
{
    let mapped: Vec<U> = list.iter().cloned().map(&f).collect();
    let lhs = mapped.first();
    let rhs = list.first().cloned().map(f);
    lhs == rhs.as_ref()
}

fn main() {
    // Natural transformation: list → option
    println!(
        "list_to_option([1,2,3]) = {:?}",
        list_to_option(&[1, 2, 3])
    );
    println!("list_to_option([]) = {:?}", list_to_option::<i32>(&[]));

    // Natural transformation: option → list
    println!("option_to_list(Some(42)) = {:?}", option_to_list(Some(42)));
    println!("option_to_list(None) = {:?}", option_to_list::<i32>(None));

    // Verify the naturality condition: map f . nat = nat . map f
    let holds = naturality_holds(&[1i32, 2, 3], |x| x * 2);
    println!("Naturality condition holds for [1,2,3] with f=(*2): {holds}");

    let holds_empty = naturality_holds::<i32, i32, _>(&[], |x| x * 2);
    println!("Naturality condition holds for [] with f=(*2): {holds_empty}");

    // Recursive version matches idiomatic
    println!(
        "list_to_option_rec([1,2,3]) = {:?}",
        list_to_option_rec(&[1, 2, 3])
    );
}

/* Output:
   list_to_option([1,2,3]) = Some(1)
   list_to_option([]) = None
   option_to_list(Some(42)) = [42]
   option_to_list(None) = []
   Naturality condition holds for [1,2,3] with f=(*2): true
   Naturality condition holds for [] with f=(*2): true
   list_to_option_rec([1,2,3]) = Some(1)
*/

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

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

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

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

    #[test]
    fn test_list_to_option_rec_matches_idiomatic() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3]];
        for &list in cases {
            assert_eq!(list_to_option(list), list_to_option_rec(list));
        }
    }

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

    #[test]
    fn test_option_to_list_some() {
        assert_eq!(option_to_list(Some(42)), vec![42]);
    }

    #[test]
    fn test_naturality_nonempty() {
        assert!(naturality_holds(&[1i32, 2, 3], |x| x * 2));
    }

    #[test]
    fn test_naturality_empty() {
        assert!(naturality_holds::<i32, i32, _>(&[], |x| x * 2));
    }
}

(* In a functor category, objects are functors and morphisms are
   natural transformations. In OCaml, functors + polymorphic functions. *)

(* Functor = type constructor with map *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

(* Natural transformation: polymorphic function between two functors *)
(* nat_trans F G = forall a. F.t a -> G.t a *)

module ListF : FUNCTOR = struct
  type 'a t = 'a list
  let map = List.map
end

module OptionF : FUNCTOR = struct
  type 'a t = 'a option
  let map = Option.map
end

(* Natural transformation: list -> option (head) *)
let list_to_option : 'a list -> 'a option = function
  | []     -> None
  | x :: _ -> Some x

(* Naturality condition: map f . nat = nat . map f *)
let check_naturality () =
  let f x = x * 2 in
  let lst = [1; 2; 3] in
  (* list_to_option (map f lst) = map f (list_to_option lst) *)
  let lhs = list_to_option (List.map f lst) in
  let rhs = Option.map f (list_to_option lst) in
  assert (lhs = rhs);
  Printf.printf "Naturality: list_to_option is a natural transformation\n"

(* Another nat trans: option -> list *)
let option_to_list : 'a option -> 'a list = function
  | None   -> []
  | Some x -> [x]

let () =
  check_naturality ();
  Printf.printf "list_to_option [1;2;3] = %s\n"
    (match list_to_option [1;2;3] with Some n -> string_of_int n | None -> "None");
  Printf.printf "option_to_list (Some 42) = [%s]\n"
    (option_to_list (Some 42) |> List.map string_of_int |> String.concat ";")

📊 Detailed Comparison

OCaml vs Rust: Functor Category — Natural Transformations

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

(* Functor interface using module signature — HKT via type 'a t *)
module type FUNCTOR = sig
type 'a t
val map : ('a -> 'b) -> 'a t -> 'b t
end

(* Natural transformation: list → option (take head) *)
let list_to_option : 'a list -> 'a option = function
| []     -> None
| x :: _ -> Some x

(* Naturality: map f . nat = nat . map f *)
let check_naturality () =
let f x = x * 2 in
let lst = [1; 2; 3] in
let lhs = list_to_option (List.map f lst) in
let rhs = Option.map f (list_to_option lst) in
assert (lhs = rhs)

Rust (idiomatic)

// Natural transformation: slice → Option, borrows in/out (no allocation)
pub fn list_to_option<T>(list: &[T]) -> Option<&T> {
 list.first()
}

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

Rust (functional/recursive)

// Same natural transformation, spelled out as a recursive pattern match
// mirroring the OCaml `function | [] -> None | x :: _ -> Some x`
pub fn list_to_option_rec<T>(list: &[T]) -> Option<&T> {
 match list {
     [] => None,
     [head, ..] => Some(head),
 }
}

// Naturality condition as a typed, generic predicate
pub fn naturality_holds<T, U, F>(list: &[T], f: F) -> bool
where
 T: Clone,
 U: PartialEq,
 F: Fn(T) -> U,
{
 let mapped: Vec<U> = list.iter().cloned().map(&f).collect();
 let lhs = mapped.first();
 let rhs = list.first().cloned().map(f);
 lhs == rhs.as_ref()
}

Type Signatures

Concept	OCaml	Rust
Functor interface	`module type FUNCTOR` with `type 'a t`	No direct equivalent (no HKT in stable Rust)
List type	`'a list`	`&[T]` (borrowed slice)
Natural transformation	`'a list -> 'a option`	`fn list_to_option<T>(list: &[T]) -> Option<&T>`
Option type	`'a option`	`Option<T>`
Map over list	`List.map f lst`	`list.iter().cloned().map(f).collect::<Vec<_>>()`
Map over option	`Option.map f opt`	`opt.map(f)`
Naturality assertion	`assert (lhs = rhs)`	`naturality_holds(list, f)` — returns `bool`

Key Insights

1. HKT gap: OCaml can express `FUNCTOR` as a module type with `type 'a t` — a higher-kinded type. Rust has no equivalent in stable code, so the functor concept remains implicit in how `Vec<T>` and `Option<T>` both support `.map()`.

2. Ownership shapes signatures: OCaml's `list_to_option` takes and returns values freely. In Rust, the idiomatic version takes a `&[T]` (a borrow) and returns `Option<&T>` — a reference into the input — avoiding any heap allocation for the common case.

3. Naturality as a first-class predicate: OCaml verifies naturality with an `assert` at runtime. Rust encodes it as `naturality_holds<T, U, F>` — a generic function whose type bounds (`T: Clone, U: PartialEq, F: Fn(T) -> U`) document exactly what the condition requires, making the proof obligation visible in the type system.

4. Pattern matching parity: The recursive Rust version (`match list { [] => None, [head, ..] => Some(head) }`) is almost a direct transliteration of OCaml's `function | [] -> None | x :: _ -> Some x`, showing how slice patterns bridge the two languages.

5. `as_ref()` for cross-ownership comparison: To compare `Option<&U>` (lhs) with `Option<U>` (rhs) in `naturality_holds`, Rust requires `rhs.as_ref()` to get `Option<&U>`. OCaml performs structural equality without worrying about ownership, illustrating how Rust's ownership model adds small but necessary boilerplate at comparison sites.

When to Use Each Style

Use idiomatic Rust (`list.first()`) when you need a fast, zero-copy check and the caller already holds the slice — the borrow is cheap and the API is maximally general.

Use recursive Rust when teaching the OCaml parallel explicitly, or when the pattern-match structure itself is the point (e.g., demonstrating structural recursion or showing the empty/non-empty case split).