🎬 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

221: Apomorphism

Difficulty: ⭐⭐⭐ Level: Recursion Schemes Anamorphism upgraded: unfold a structure but short-circuit by injecting a pre-built subtree instead of continuing.

The Problem This Solves

An anamorphism (plain unfold) builds a recursive structure step by step — at each point you return a seed for the next step. But sometimes you want to stop early and embed an already-built subtree instead of continuing to unfold. The classic example is inserting into a sorted list: once you find the right position, you want to splice in the entire remaining tail as-is, not re-unfold it element by element. With plain `ana`, there's no way to say "stop here and use this pre-existing structure." You'd have to keep unfolding until you reach the end even when you already have the rest of the list ready. This is wasteful and — more importantly — loses the intent of the algorithm. Apomorphism solves this with an `Either` type in the coalgebra's output: return `Right(new_seed)` to continue unfolding as normal, or return `Left(existing_fix)` to short-circuit and embed a pre-built subtree immediately.

The Intuition

Think of building a list like laying bricks one by one. Anamorphism forces you to lay each brick from your raw materials. Apomorphism lets you grab a pre-assembled wall section (an existing `FixList`) and slot it in directly. When inserting `3` into the sorted list `[1, 2, 4, 5]`:

At `1`: `3 > 1`, so continue — `Right([2, 4, 5])` (keep unfolding)
At `2`: `3 > 2`, so continue — `Right([4, 5])` (keep unfolding)
At `4`: `3 ≤ 4`, so we found the position — output `3` and then inject `[4, 5]` directly as `Left([4, 5])`

Without short-circuit, you'd have to "unfold" `[4, 5]` element by element even though you already have it. With apomorphism, you say "stop — here's the rest." `Either::Left(fix)` = "done, embed this" `Either::Right(seed)` = "continue from this seed"

How It Works in Rust

// Either: Left = pre-built Fix (stop), Right = seed (continue)
enum Either<L, R> { Left(L), Right(R) }

// apo: coalgebra returns F<Either<Fix, Seed>>
fn apo<S>(coalg: &dyn Fn(S) -> ListF<Either<FixList, S>>, seed: S) -> FixList {
 FixList(Box::new(coalg(seed).map(|either| match either {
     Either::Left(fix) => fix,          // short-circuit: use pre-built subtree
     Either::Right(s) => apo(coalg, s), // continue unfolding from new seed
 })))
}

Insert into sorted list:

fn insert(x: i64, lst: FixList) -> FixList {
 apo(&|fl: FixList| match fl.0.as_ref() {
     ListF::NilF =>
         // Reached the end: insert x before the empty list
         ListF::ConsF(x, Either::Left(nil())),
     ListF::ConsF(y, rest) => {
         if x <= *y {
             // Found position: output x, then inject the rest unchanged
             ListF::ConsF(x, Either::Left(fl.clone()))  // ← short-circuit here
         } else {
             // Keep going: output y, continue from rest
             ListF::ConsF(*y, Either::Right(rest.clone())) // ← continue
         }
     }
 }, lst)
}

The `Either::Left(fl.clone())` is the key: instead of re-unfolding the tail, we hand back the existing `FixList` directly.

What This Unlocks

Sorted insertion — the prototypical use: insert one element without disturbing the already-sorted tail.
`take` / `replace-first` — any operation that wants to stop after a condition is met and preserve the rest structurally.
Efficient list transformations — avoid redundant unfolding when a suffix is already computed; share structure explicitly.

Key Differences

Concept	OCaml	Rust
Either type	Custom `('a, 'b) either` sum type	Custom `Either<L, R>` enum
Short-circuit syntax	`Left fix` (shared reference)	`Left(fix.clone())` (clone required)
Coalgebra output	`'f (fix either seed)`	`ListF<Either<FixList, S>>`
vs anamorphism	No early exit possible	`Either::Left` = early exit
Memory model	GC shares the injected subtree	Clone at injection point

// Example 221: Apomorphism — Ana that Can Short-Circuit

#[derive(Debug, Clone)]
enum ListF<A> { NilF, ConsF(i64, A) }

impl<A> ListF<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> ListF<B> {
        match self { ListF::NilF => ListF::NilF, ListF::ConsF(x, a) => ListF::ConsF(x, f(a)) }
    }
}

#[derive(Debug, Clone)]
struct FixList(Box<ListF<FixList>>);

fn nil() -> FixList { FixList(Box::new(ListF::NilF)) }
fn cons(x: i64, xs: FixList) -> FixList { FixList(Box::new(ListF::ConsF(x, xs))) }

fn to_vec(fl: &FixList) -> Vec<i64> {
    let mut result = vec![];
    let mut cur = fl;
    loop {
        match cur.0.as_ref() {
            ListF::NilF => break,
            ListF::ConsF(x, rest) => { result.push(*x); cur = rest; }
        }
    }
    result
}

// Either: Left = pre-built Fix (stop), Right = seed (continue)
enum Either<L, R> { Left(L), Right(R) }

// apo: coalgebra returns F<Either<Fix, Seed>>
fn apo<S>(coalg: &dyn Fn(S) -> ListF<Either<FixList, S>>, seed: S) -> FixList {
    FixList(Box::new(coalg(seed).map(|either| match either {
        Either::Left(fix) => fix,         // short-circuit
        Either::Right(s) => apo(coalg, s), // continue
    })))
}

// Approach 1: Insert into sorted list
fn insert(x: i64, lst: FixList) -> FixList {
    apo(&|fl: FixList| match fl.0.as_ref() {
        ListF::NilF => ListF::ConsF(x, Either::Left(nil())),
        ListF::ConsF(y, rest) => {
            if x <= *y {
                ListF::ConsF(x, Either::Left(fl.clone()))
            } else {
                ListF::ConsF(*y, Either::Right(rest.clone()))
            }
        }
    }, lst)
}

// Approach 2: Take n elements
fn take(n: usize, lst: FixList) -> FixList {
    apo(&|s: (usize, FixList)| {
        let (n, fl) = s;
        if n == 0 { return ListF::NilF; }
        match fl.0.as_ref() {
            ListF::NilF => ListF::NilF,
            ListF::ConsF(x, rest) => ListF::ConsF(*x, Either::Right((n - 1, rest.clone()))),
        }
    }, (n, lst))
}

// Approach 3: Replace first occurrence
fn replace_first(target: i64, replacement: i64, lst: FixList) -> FixList {
    apo(&|fl: FixList| match fl.0.as_ref() {
        ListF::NilF => ListF::NilF,
        ListF::ConsF(x, rest) => {
            if *x == target {
                ListF::ConsF(replacement, Either::Left(rest.clone()))
            } else {
                ListF::ConsF(*x, Either::Right(rest.clone()))
            }
        }
    }, lst)
}

fn main() {
    let sorted = cons(1, cons(3, cons(5, nil())));
    assert_eq!(to_vec(&insert(2, sorted.clone())), vec![1, 2, 3, 5]);
    assert_eq!(to_vec(&insert(0, sorted.clone())), vec![0, 1, 3, 5]);
    assert_eq!(to_vec(&insert(6, sorted.clone())), vec![1, 3, 5, 6]);

    let xs = cons(1, cons(2, cons(3, cons(4, cons(5, nil())))));
    assert_eq!(to_vec(&take(3, xs.clone())), vec![1, 2, 3]);
    assert_eq!(to_vec(&take(0, xs.clone())), vec![]);
    assert_eq!(to_vec(&take(10, xs.clone())), vec![1, 2, 3, 4, 5]);

    let xs2 = cons(1, cons(2, cons(3, cons(2, nil()))));
    assert_eq!(to_vec(&replace_first(2, 99, xs2)), vec![1, 99, 3, 2]);

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

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

    #[test]
    fn test_insert_middle() {
        let l = cons(1, cons(3, nil()));
        assert_eq!(to_vec(&insert(2, l)), vec![1, 2, 3]);
    }

    #[test]
    fn test_take_empty() {
        assert_eq!(to_vec(&take(5, nil())), vec![]);
    }

    #[test]
    fn test_replace_not_found() {
        let l = cons(1, cons(2, nil()));
        assert_eq!(to_vec(&replace_first(99, 0, l)), vec![1, 2]);
    }
}

(* Example 221: Apomorphism — Ana that Can Short-Circuit *)

(* apo : ('a -> 'f (Either fix 'a)) -> 'a -> fix
   Like ana, but at each step you can either:
   - Right seed: continue unfolding
   - Left fix:   inject a pre-built subtree (short-circuit) *)

type 'a list_f = NilF | ConsF of int * 'a

let map_f f = function NilF -> NilF | ConsF (x, a) -> ConsF (x, f a)

type fix_list = FixL of fix_list list_f

let rec ana coalg seed = FixL (map_f (ana coalg) (coalg seed))

(* apo: coalgebra returns Either fix_list seed *)
let rec apo coalg seed =
  let layer = coalg seed in
  FixL (map_f (function
    | Either.Left fix -> fix        (* pre-built, stop *)
    | Either.Right s -> apo coalg s (* continue unfolding *)
  ) layer)

(* Since OCaml doesn't have Either built-in, define it *)
type ('a, 'b) either = Left of 'a | Right of 'b

let rec apo coalg seed =
  let layer = coalg seed in
  FixL (map_f (function
    | Left fix -> fix
    | Right s -> apo coalg s
  ) layer)

(* Approach 1: Insert into sorted list — short-circuit with remainder *)
let insert_coalg x = function
  | FixL NilF -> ConsF (x, Left (FixL NilF))
  | FixL (ConsF (y, rest)) as original ->
    if x <= y then ConsF (x, Left original)  (* short-circuit: keep rest as-is *)
    else ConsF (y, Right rest)                 (* continue searching *)

let insert x lst = apo (insert_coalg x) lst

(* Approach 2: Take n elements — short-circuit after n *)
let take_coalg n = function
  | _, FixL NilF -> NilF
  | 0, _ -> NilF
  | n, FixL (ConsF (x, rest)) ->
    ConsF (x, Right (n - 1, rest))

let take n lst = apo (fun (n, lst) -> take_coalg n (n, lst)) (n, lst)

(* Approach 3: Replace first occurrence *)
let replace_first_coalg (target, replacement) = function
  | FixL NilF -> NilF
  | FixL (ConsF (x, rest)) ->
    if x = target then ConsF (replacement, Left rest)  (* found it, short-circuit *)
    else ConsF (x, Right rest)  (* keep looking *)

let replace_first target replacement lst =
  apo (replace_first_coalg (target, replacement)) lst

(* Helpers *)
let nil = FixL NilF
let cons x xs = FixL (ConsF (x, xs))
let rec to_list (FixL f) = match f with
  | NilF -> []
  | ConsF (x, rest) -> x :: to_list rest

(* === Tests === *)
let () =
  let sorted = cons 1 (cons 3 (cons 5 nil)) in

  (* Insert *)
  assert (to_list (insert 2 sorted) = [1; 2; 3; 5]);
  assert (to_list (insert 0 sorted) = [0; 1; 3; 5]);
  assert (to_list (insert 6 sorted) = [1; 3; 5; 6]);

  (* Take *)
  let xs = cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))) in
  assert (to_list (take 3 xs) = [1; 2; 3]);
  assert (to_list (take 0 xs) = []);
  assert (to_list (take 10 xs) = [1; 2; 3; 4; 5]);

  (* Replace first *)
  let xs2 = cons 1 (cons 2 (cons 3 (cons 2 nil))) in
  assert (to_list (replace_first 2 99 xs2) = [1; 99; 3; 2]);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 221 — Apomorphism

apo Definition

OCaml

🐪 Show OCaml equivalent

let rec apo coalg seed =
FixL (map_f (function
 | Left fix -> fix
 | Right s -> apo coalg s
) (coalg seed))

Rust

fn apo<S>(coalg: &dyn Fn(S) -> ListF<Either<FixList, S>>, seed: S) -> FixList {
 FixList(Box::new(coalg(seed).map(|either| match either {
     Either::Left(fix) => fix,
     Either::Right(s) => apo(coalg, s),
 })))
}

Insert into Sorted List

OCaml

🐪 Show OCaml equivalent

let insert_coalg x = function
| FixL NilF -> ConsF (x, Left (FixL NilF))
| FixL (ConsF (y, rest)) as original ->
 if x <= y then ConsF (x, Left original)   (* short-circuit *)
 else ConsF (y, Right rest)                  (* continue *)

Rust

apo(&|fl: FixList| match fl.0.as_ref() {
 ListF::NilF => ListF::ConsF(x, Either::Left(nil())),
 ListF::ConsF(y, rest) =>
     if x <= *y { ListF::ConsF(x, Either::Left(fl.clone())) }
     else { ListF::ConsF(*y, Either::Right(rest.clone())) },
}, lst)

221: Apomorphism

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 221 — Apomorphism

apo Definition

OCaml

Rust

Insert into Sorted List

OCaml

Rust

Related Examples