🎬 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

226: Category Theory Basics

Difficulty: Expert Level: 4 A category is just: objects + arrows + associative composition. That's the complete foundation for reasoning about programs algebraically.

The Problem This Solves

Programming is full of patterns that look superficially different but are structurally identical. Function composition. Monad chaining. Parser combination. Option/Result chaining. All of these share the same shape: you connect things together, the connection is associative, and there's a neutral "do nothing" element. But without a common vocabulary, we describe each one separately and miss the deeper unity. Category theory provides that vocabulary. Once you see that Rust's type system, function composition, and monad operations are all instances of the same categorical structure, you can reason about them uniformly. You know what laws they must satisfy, what transformations are safe, and why `map` over `Option`, `Vec`, and `Result` all feel the same. This example introduces the core machinery: categories as `compose` + `identity`, and the Kleisli category as the categorical model of monadic computation.

The Intuition

A category has three things: 1. Objects — in Rust, these are types (`i32`, `String`, `Vec<u8>`, your structs) 2. Arrows (morphisms) — in Rust, these are functions (`fn(A) -> B`) 3. Composition — chaining arrows: `f: A→B` and `g: B→C` give `g∘f: A→C` Two laws must hold:

Associativity: `(h∘g)∘f = h∘(g∘f)` — grouping doesn't matter when composing
Identity: there's an arrow `id: A→A` where `f∘id = f` and `id∘f = f` — "do nothing" composes neutrally

In Rust: `identity<A>(a: A) -> A { a }` is the identity arrow. `compose(f, g)` chains them. The Kleisli category is what you get when all arrows have the shape `A -> M<B>` (for some wrapper `M`). In Rust: `A -> Option<B>`, `A -> Result<B, E>`, `A -> Vec<B>`. Kleisli composition is exactly monadic `and_then`. This is why every monad is secretly a category. Think of it like plumbing: objects are pipe sizes, morphisms are pipe segments, composition is connecting segments end-to-end, and identity is a straight-through segment.

How It Works in Rust

// Identity arrow: every type A has one
fn identity<A>(a: A) -> A { a }

// Composition: f after g
fn compose<A, B, C>(f: impl Fn(B) -> C, g: impl Fn(A) -> B) -> impl Fn(A) -> C {
 move |a| f(g(a))
}

// Category as a trait (explicit abstraction)
trait Category {
 type Obj;
 fn id() -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
 fn compose(
     f: Box<dyn Fn(Self::Obj) -> Self::Obj>,
     g: Box<dyn Fn(Self::Obj) -> Self::Obj>,
 ) -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
}

// Kleisli category: arrows are A -> Option<B>
// Composition is exactly monadic and_then
fn kleisli_compose<A, B, C>(
 f: impl Fn(B) -> Option<C>,
 g: impl Fn(A) -> Option<B>,
) -> impl Fn(A) -> Option<C> {
 move |a| g(a).and_then(|b| f(b))  // this IS categorical composition in Kleisli
}

fn kleisli_id<A>(a: A) -> Option<A> { Some(a) }  // identity in Kleisli = Some

Verify the laws hold:

// Associativity: compose(h, compose(g, f)) == compose(compose(h, g), f)
// Identity: compose(f, identity) == f  and  compose(identity, f) == f
// These are checked in the tests — violating them means it's not a category

What This Unlocks

Principled composition — any type that forms a category gets `compose` and `id` for free, with laws that guarantee safe refactoring.
Kleisli as monad model — understanding that `and_then`/`flat_map` is categorical composition explains why monad laws look the way they do.
Abstract reasoning — once you identify a categorical structure in your code, you immediately know what holds (associativity, identity) without proof.

Key Differences

Concept	OCaml	Rust
Category abstraction	Module signature `CATEGORY`	`trait Category`
Composition	`let compose f g x = f (g x)`	`fn compose<A,B,C>` with move closure
Kleisli arrows	`a -> b option`	`impl Fn(A) -> Option<B>`
Kleisli composition	`Option.bind` / `>>=`	`.and_then()`
Objects	Types in a module	Types as `type Obj` in trait

// Example 226: Category Basics
// A category has objects, morphisms, composition, and identity.
// In Rust: types = objects, functions = morphisms.

// === Approach 1: Simple compose and identity functions ===

fn identity<A>(a: A) -> A {
    a
}

fn compose<A, B, C>(f: impl Fn(B) -> C, g: impl Fn(A) -> B) -> impl Fn(A) -> C {
    move |a| f(g(a))
}

// === Approach 2: Category trait (explicit abstraction) ===

trait Category {
    type Obj;
    // We represent morphisms as boxed closures for flexibility
    fn id() -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
    fn compose(
        f: Box<dyn Fn(Self::Obj) -> Self::Obj>,
        g: Box<dyn Fn(Self::Obj) -> Self::Obj>,
    ) -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
}

struct FnCategoryI32;

impl Category for FnCategoryI32 {
    type Obj = i32;

    fn id() -> Box<dyn Fn(i32) -> i32> {
        Box::new(|x| x)
    }

    fn compose(
        f: Box<dyn Fn(i32) -> i32>,
        g: Box<dyn Fn(i32) -> i32>,
    ) -> Box<dyn Fn(i32) -> i32> {
        Box::new(move |x| f(g(x)))
    }
}

// === Approach 3: Kleisli category (a -> Option<b>) ===

fn kleisli_id<A>(a: A) -> Option<A> {
    Some(a)
}

fn kleisli_compose<A, B, C>(
    f: impl Fn(B) -> Option<C> + 'static,
    g: impl Fn(A) -> Option<B> + 'static,
) -> impl Fn(A) -> Option<C> {
    move |a| g(a).and_then(|b| f(b))
}

fn main() {
    // Approach 1: compose and identity
    let f = |x: i32| x + 1;
    let g = |x: i32| x * 2;
    let h = |x: i32| x - 3;

    let fg = compose(f, g);
    assert_eq!(fg(5), 11); // (5*2)+1

    // Left identity: compose(id, f) = f
    assert_eq!(compose(identity, f)(5), f(5));
    // Right identity: compose(f, id) = f
    assert_eq!(compose(f, identity)(5), f(5));
    // Associativity: compose(compose(f,g), h) = compose(f, compose(g,h))
    assert_eq!(compose(compose(f, g), h)(10), compose(f, compose(g, h))(10));
    println!("Approach 1 - Category laws verified");

    // Approach 2: Explicit Category trait
    let inc: Box<dyn Fn(i32) -> i32> = Box::new(|x| x + 1);
    let dbl: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);
    let composed = FnCategoryI32::compose(inc, dbl);
    assert_eq!(composed(5), 11);
    println!("Approach 2 - FnCategory works: compose(+1, *2)(5) = {}", composed(5));

    // Approach 3: Kleisli category
    let safe_div = |x: i32| -> Option<i32> {
        if x == 0 { None } else { Some(100 / x) }
    };
    let safe_succ = |x: i32| -> Option<i32> { Some(x + 1) };

    let k = kleisli_compose(safe_succ, safe_div);
    assert_eq!(k(5), Some(21));
    assert_eq!(k(0), None);

    // Identity laws
    let k_id_left = kleisli_compose(kleisli_id, safe_div);
    assert_eq!(k_id_left(5), safe_div(5));
    let k_id_right = kleisli_compose(safe_div, kleisli_id);
    assert_eq!(k_id_right(5), safe_div(5));
    println!("Approach 3 - Kleisli category verified");

    println!("✓ All tests passed");
}

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

    #[test]
    fn test_compose_basic() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        assert_eq!(compose(f, g)(5), 11);
    }

    #[test]
    fn test_identity_laws() {
        let f = |x: i32| x + 1;
        assert_eq!(compose(identity, f)(10), f(10));
        assert_eq!(compose(f, identity)(10), f(10));
    }

    #[test]
    fn test_associativity() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        let h = |x: i32| x - 3;
        assert_eq!(
            compose(compose(f, g), h)(7),
            compose(f, compose(g, h))(7)
        );
    }

    #[test]
    fn test_kleisli_compose() {
        let safe_div = |x: i32| -> Option<i32> {
            if x == 0 { None } else { Some(100 / x) }
        };
        let safe_succ = |x: i32| -> Option<i32> { Some(x + 1) };
        let k = kleisli_compose(safe_succ, safe_div);
        assert_eq!(k(5), Some(21));
        assert_eq!(k(0), None);
    }
}

(* Example 226: Category Basics *)
(* A category has objects, morphisms, composition, and identity *)

(* === Approach 1: Category as composition and identity === *)

(* In OCaml, types are objects and functions are morphisms.
   Composition is (.) and identity is Fun.id *)

let compose f g x = f (g x)
let id x = x

(* Category laws:
   1. Left identity:  compose id f = f
   2. Right identity: compose f id = f
   3. Associativity:  compose (compose f g) h = compose f (compose g h) *)

let () =
  let f x = x + 1 in
  let g x = x * 2 in
  let h x = x - 3 in
  (* Left identity *)
  assert (compose id f 5 = f 5);
  (* Right identity *)
  assert (compose f id 5 = f 5);
  (* Associativity *)
  assert (compose (compose f g) h 10 = compose f (compose g h) 10);
  Printf.printf "Approach 1 - Category laws verified\n"

(* === Approach 2: Explicit Category module type === *)

module type CATEGORY = sig
  type ('a, 'b) morphism
  val id : ('a, 'a) morphism
  val compose : ('b, 'c) morphism -> ('a, 'b) morphism -> ('a, 'c) morphism
end

(* The category of OCaml types and functions *)
module FnCategory : CATEGORY with type ('a, 'b) morphism = 'a -> 'b = struct
  type ('a, 'b) morphism = 'a -> 'b
  let id x = x
  let compose f g x = f (g x)
end

let () =
  let open FnCategory in
  let f = fun x -> x + 1 in
  let g = fun x -> x * 2 in
  let result = compose f g 5 in
  assert (result = 11);
  assert (compose id f 5 = f 5);
  Printf.printf "Approach 2 - FnCategory works: compose (+1) (*2) 5 = %d\n" result

(* === Approach 3: Kleisli category (morphisms a -> 'b option) === *)

module KleisliOption = struct
  type ('a, 'b) morphism = 'a -> 'b option
  let id x = Some x
  let compose f g x =
    match g x with
    | None -> None
    | Some y -> f y
end

let () =
  let open KleisliOption in
  let safe_div x = if x = 0 then None else Some (100 / x) in
  let safe_succ x = Some (x + 1) in
  assert (compose safe_succ safe_div 5 = Some 21);
  assert (compose safe_succ safe_div 0 = None);
  (* Identity law *)
  assert (compose id safe_div 5 = safe_div 5);
  assert (compose safe_div id 5 = safe_div 5);
  Printf.printf "Approach 3 - Kleisli category verified\n"

let () = Printf.printf "✓ All tests passed\n"