🎬 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

222: Histomorphism

Difficulty: ⭐⭐⭐ Level: Recursion Schemes Fold a recursive structure with access to the entire computation history at each step — not just the previous result, but every result computed so far.

The Problem This Solves

Computing Fibonacci numbers naively is exponential — `fib(n)` calls `fib(n-1)` and `fib(n-2)`, each of which re-computes everything below them. The standard fix is a memoization table. But there's a deeper fix: use a fold that structurally carries all previous answers along with it. A catamorphism gives you one result per recursive call. A paramorphism gives you the result plus the original subterm. A histomorphism goes further: at each step you see a chain of all results computed on the way here. This is the structure of dynamic programming made explicit — instead of a mutable cache, you have an immutable `Cofree` chain that IS the memo table. The result: Fibonacci in O(n) with no memoization table, no mutation, and no imperative loops — just a fold that carries its own history.

The Intuition

Imagine computing `fib(5)`. You need `fib(4)` and `fib(3)`. But by the time you're computing `fib(5)`, you've already computed `fib(4)`, `fib(3)`, `fib(2)`, `fib(1)`, and `fib(0)` — they're all sitting in a chain below you. A histomorphism threads this chain through the fold as a `Cofree` structure. `Cofree` means "free comonad" but you can read it as: a value with its history attached. Each node in the `Cofree` chain has:

`head`: the result computed here
`tail`: the rest of the history (what was computed before this)

At `fib(5)`, the algebra looks at the `Cofree` chain and can reach back to `fib(4)` (one step) and `fib(3)` (two steps) by navigating `.tail`.

Cofree chain for nat(5):
head=fib(5)
tail → head=fib(4)
      tail → head=fib(3)
             tail → head=fib(2)
                    tail → head=fib(1)
                           tail → head=fib(0)
                                  tail → ZeroF

How It Works in Rust

// Cofree: result + history
struct Cofree<A> {
 head: A,                      // result computed at this position
 tail: Box<NatF<Cofree<A>>>,   // the history: NatF wrapping more Cofree nodes
}

// histo: build cofree bottom-up, algebra sees history chain
fn histo<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> A {
 histo_build(alg, fix).head
}

fn histo_build<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> Cofree<A> {
 let layer = fix.0.map_ref(|child| histo_build(alg, child)); // recurse first
 let result = alg(layer.clone());                             // compute result
 Cofree::new(result, layer)                                   // attach history
}

Fibonacci algebra — looks back 2 steps via the `Cofree` chain:

fn fib_alg(n: NatF<Cofree<u64>>) -> u64 {
 match n {
     NatF::ZeroF => 0,                // fib(0) = 0
     NatF::SuccF(prev) => match prev.tail.as_ref() {
         NatF::ZeroF => 1,            // fib(1) = 1
         NatF::SuccF(prev2) =>
             prev.head + prev2.head,  // fib(n) = fib(n-1) + fib(n-2)
                                      // prev.head = fib(n-1), prev2.head = fib(n-2)
     }
 }
}

Each `Cofree` node carries all previous `head` values in the chain — the algebra just navigates as far back as needed.

What This Unlocks

Dynamic programming without mutation — any DP recurrence (Fibonacci, tribonacci, Pascal's triangle) becomes a histomorphism; the `Cofree` chain is the memo table.
Sliding-window computations — when you need the last `k` computed values at each step, navigate `k` levels into the `Cofree` chain.
Proof of O(n) — because the `Cofree` chain shares nodes built during the recursion, each value is computed exactly once.

Key Differences

Concept	OCaml	Rust
Cofree type	Recursive `'a cofree_nat = CF of 'a * ...`	`struct Cofree<A> { head, tail: Box<NatF<...>> }`
History access	Pattern match nested `CF` constructors	`.tail.as_ref()` then match
vs catamorphism	Only current result	Entire history chain
vs paramorphism	One level of original	All levels of computed results
Performance	O(n), GC shares history	O(n), but clones at each layer

// Example 222: Histomorphism — Cata with Full History (Fibonacci in O(n))

// histo: algebra sees all previous results via Cofree

#[derive(Debug, Clone)]
enum NatF<A> { ZeroF, SuccF(A) }

impl<A> NatF<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> NatF<B> {
        match self { NatF::ZeroF => NatF::ZeroF, NatF::SuccF(a) => NatF::SuccF(f(a)) }
    }
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> NatF<B> {
        match self { NatF::ZeroF => NatF::ZeroF, NatF::SuccF(a) => NatF::SuccF(f(a)) }
    }
}

// Cofree: result + history
#[derive(Debug, Clone)]
struct Cofree<A> {
    head: A,
    tail: Box<NatF<Cofree<A>>>,
}

impl<A> Cofree<A> {
    fn new(head: A, tail: NatF<Cofree<A>>) -> Self {
        Cofree { head, tail: Box::new(tail) }
    }
}

#[derive(Debug, Clone)]
struct FixNat(Box<NatF<FixNat>>);

fn zero() -> FixNat { FixNat(Box::new(NatF::ZeroF)) }
fn succ(n: FixNat) -> FixNat { FixNat(Box::new(NatF::SuccF(n))) }
fn nat(n: u32) -> FixNat { (0..n).fold(zero(), |acc, _| succ(acc)) }

// histo: build cofree bottom-up, algebra sees history chain
fn histo<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> A {
    histo_build(alg, fix).head
}

fn histo_build<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> Cofree<A> {
    let layer = fix.0.map_ref(|child| histo_build(alg, child));
    let result = alg(layer.clone());
    Cofree::new(result, layer)
}

// NatF derives Clone, which covers NatF<Cofree<A>> when A: Clone

// Approach 1: Fibonacci — algebra looks back 2 steps
fn fib_alg(n: NatF<Cofree<u64>>) -> u64 {
    match n {
        NatF::ZeroF => 0,
        NatF::SuccF(cf) => match cf.tail.as_ref() {
            NatF::ZeroF => 1,  // fib(1) = 1
            NatF::SuccF(cf2) => cf.head + cf2.head,  // fib(n-1) + fib(n-2)
        }
    }
}

// Approach 2: Tribonacci — looks back 3 steps
fn trib_alg(n: NatF<Cofree<u64>>) -> u64 {
    match n {
        NatF::ZeroF => 0,
        NatF::SuccF(cf) => match cf.tail.as_ref() {
            NatF::ZeroF => 0,  // trib(1) = 0
            NatF::SuccF(cf2) => match cf2.tail.as_ref() {
                NatF::ZeroF => 1,  // trib(2) = 1
                NatF::SuccF(cf3) => cf.head + cf2.head + cf3.head,
            }
        }
    }
}

// Approach 3: General "look back n" pattern
fn lucas_alg(n: NatF<Cofree<u64>>) -> u64 {
    match n {
        NatF::ZeroF => 2,
        NatF::SuccF(cf) => match cf.tail.as_ref() {
            NatF::ZeroF => 1,
            NatF::SuccF(cf2) => cf.head + cf2.head,
        }
    }
}

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

    #[test] fn test_fib_20() { assert_eq!(histo(&fib_alg, &nat(20)), 6765); }
    #[test] fn test_trib_7() { assert_eq!(histo(&trib_alg, &nat(7)), 13); }
    #[test] fn test_lucas_6() { assert_eq!(histo(&lucas_alg, &nat(6)), 18); }
}

(* Example 222: Histomorphism — Cata with Full History *)

(* histo : ('f (Cofree 'f 'a) -> 'a) -> fix -> 'a
   Like cata, but the algebra sees ALL previous results (not just immediate children).
   Uses Cofree comonad to store history at each node. *)

(* Cofree: a value paired with a functor of more cofree values *)
type 'a nat_f = ZeroF | SuccF of 'a

let map_nat f = function ZeroF -> ZeroF | SuccF a -> SuccF (f a)

type ('f, 'a) cofree = Cofree of 'a * ('f, 'a) cofree nat_f
(* Simplified: for nat_f specifically *)
type 'a cofree_nat = CF of 'a * 'a cofree_nat nat_f

let head (CF (a, _)) = a
let tail (CF (_, t)) = t

type fix_nat = FixN of fix_nat nat_f

let rec cata alg (FixN f) = alg (map_nat (cata alg) f)

(* histo: builds up cofree at each step *)
let rec histo alg (FixN f) =
  let cf = map_nat (fun child ->
    let result = histo alg child in
    CF (result, map_nat (fun c -> CF (histo alg c, ZeroF)) (match child with FixN g -> g))
  ) f in
  (* Simplified: use cata to build cofree, then extract *)
  alg cf

(* Simpler practical implementation using memoization-style *)
let rec histo_simple alg (FixN f) =
  alg (map_nat (histo_build alg) f)
and histo_build alg node =
  let result = histo_simple alg node in
  CF (result, map_nat (histo_build alg) (match node with FixN g -> g))

(* Approach 1: Fibonacci in O(n) via histomorphism *)
(* The algebra sees fib(n-1) AND fib(n-2) through the cofree chain *)
let fib_alg = function
  | ZeroF -> 0  (* fib(0) = 0 *)
  | SuccF (CF (n1, ZeroF)) -> max 1 n1  (* fib(1) = 1 *)
  | SuccF (CF (n1, SuccF (CF (n2, _)))) -> n1 + n2  (* fib(n) = fib(n-1) + fib(n-2) *)

(* Build a natural number as fix_nat *)
let zero = FixN ZeroF
let succ n = FixN (SuccF n)
let rec nat_of_int n = if n <= 0 then zero else succ (nat_of_int (n - 1))

let fib n = histo_simple fib_alg (nat_of_int n)

(* Approach 2: Tribonacci *)
let trib_alg = function
  | ZeroF -> 0
  | SuccF (CF (_, ZeroF)) -> 0
  | SuccF (CF (_, SuccF (CF (_, ZeroF)))) -> 1
  | SuccF (CF (n1, SuccF (CF (n2, SuccF (CF (n3, _)))))) -> n1 + n2 + n3

let trib n = histo_simple trib_alg (nat_of_int n)

(* Approach 3: Coin change with lookahead *)
(* How many ways to make change for n cents using coins [1; 5; 10]? *)
(* This is hard with plain cata but natural with histo *)

(* === Tests === *)
let () =
  (* Fibonacci *)
  assert (fib 0 = 0);
  assert (fib 1 = 1);
  assert (fib 2 = 1);
  assert (fib 5 = 5);
  assert (fib 10 = 55);

  (* Tribonacci: 0,0,1,1,2,4,7,13,24,44 *)
  assert (trib 0 = 0);
  assert (trib 2 = 1);
  assert (trib 4 = 2);
  assert (trib 6 = 7);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 222 — Histomorphism

Cofree Type

OCaml

🐪 Show OCaml equivalent

type 'a cofree_nat = CF of 'a * 'a cofree_nat nat_f
let head (CF (a, _)) = a
let tail (CF (_, t)) = t

Rust

struct Cofree<A> {
 head: A,
 tail: Box<NatF<Cofree<A>>>,
}

Fibonacci Algebra (Look Back 2 Steps)

OCaml

🐪 Show OCaml equivalent

let fib_alg = function
| ZeroF -> 0
| SuccF (CF (n1, ZeroF)) -> max 1 n1
| SuccF (CF (n1, SuccF (CF (n2, _)))) -> n1 + n2

Rust

fn fib_alg(n: NatF<Cofree<u64>>) -> u64 {
 match n {
     NatF::ZeroF => 0,
     NatF::SuccF(cf) => match cf.tail.as_ref() {
         NatF::ZeroF => 1,
         NatF::SuccF(cf2) => cf.head + cf2.head,
     }
 }
}

histo Implementation

OCaml

🐪 Show OCaml equivalent

let rec histo_simple alg (FixN f) =
alg (map_nat (histo_build alg) f)
and histo_build alg node =
let result = histo_simple alg node in
CF (result, map_nat (histo_build alg) (match node with FixN g -> g))

Rust

fn histo<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> A {
 histo_build(alg, fix).head
}
fn histo_build<A: Clone>(alg: &dyn Fn(NatF<Cofree<A>>) -> A, fix: &FixNat) -> Cofree<A> {
 let layer = fix.0.map_ref(|child| histo_build(alg, child));
 let result = alg(layer.clone());
 Cofree::new(result, layer)
}

222: Histomorphism

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 222 — Histomorphism

Cofree Type

OCaml

Rust

Fibonacci Algebra (Look Back 2 Steps)

OCaml

Rust

histo Implementation

OCaml

Rust

Related Examples