🎬 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

220: Paramorphism

Difficulty: ⭐⭐⭐ Level: Recursion Schemes Catamorphism upgraded: fold a recursive structure while keeping the original subterms in view at each step.

The Problem This Solves

A catamorphism (plain fold) gives you only the computed result at each recursive position — you can see that the tail of `[1,2,3]` folded to `6`, but you've lost the actual list `[2,3]`. Sometimes that's not enough. Computing `tails` of a list requires you to see the original tail alongside its fold result. Computing a sliding window requires the same. A plain `fold` loses the structure too early. Paramorphism solves this by giving the algebra both pieces of information at once: the computed result from the recursive call and the original subtree it came from. You can think of it as "fold with a memory" — at each step you get `(result_so_far, original_substructure)`. The name comes from Greek para (beside) — the original subterm sits beside the recursive result, always available.

The Intuition

Imagine you're folding a list from right to left. With a plain fold, when you're at element `x`, you only see what the rest computed to. With a paramorphism, when you're at element `x`, you see two things: (1) what the rest computed to, and (2) the actual list that came after `x`. Real example: computing all tails of `[1, 2, 3]` gives `[[1,2,3], [2,3], [3], []]`. To produce the sublist `[2,3]` when processing element `1`, you need access to the original remainder `[2,3]` — not just whatever it computed to. A fold would have thrown that structure away. Factorial with access to `n-1` is the canonical numeric example: `n! = n * (n-1)!` where you need both `(n-1)!` (the fold result) and `n-1` (the original subterm, as a `FixNat`). Para algebra type: `ListF<(A, FixList)> -> A` — every child becomes a pair of `(result, original)`.

How It Works in Rust

// para: algebra gets (result, original_subtree) for each child
fn para<A: Clone>(alg: &dyn Fn(ListF<(A, FixList)>) -> A, fl: &FixList) -> A {
 // For every child node, recursively compute (result, clone of original)
 let paired = fl.0.map_ref(|child| (para(alg, child), child.clone()));
 alg(paired)
}

Step by step: 1. For each child in the current layer, recurse to get result `A` 2. Clone the original child `FixList` to keep it alongside 3. Pass `(A, FixList)` pairs to the algebra — algebra sees both 4. Algebra decides what to do: use the result, the original, or both Computing `tails` with paramorphism:

fn tails(fl: &FixList) -> Vec<Vec<i64>> {
 para(&|l: ListF<(Vec<Vec<i64>>, FixList)>| match l {
     ListF::NilF => vec![vec![]],                          // base: just empty tail
     ListF::ConsF(_, (rest_tails, original_tail)) => {
         // original_tail is the actual FixList after this element
         let mut v = vec![to_vec(&original_tail)];        // this suffix as a vec
         v.extend(rest_tails);                             // all smaller suffixes
         v
     }
 }, fl)
}

The key line is `to_vec(&original_tail)` — this is only possible because paramorphism preserved `original_tail` for us.

What This Unlocks

Tails / inits / sliding windows — any operation that needs sublist views during the fold, not just the accumulated result.
Factorial and similar — numeric recursions where you need `n-1` as a value, not just `(n-1)!` as a result.
Tree diffing — compare subtrees structurally during a fold, using the original fragments for context-sensitive decisions.

Key Differences

Concept	OCaml	Rust
Algebra signature	`ListF ('a * fix) -> 'a`	`ListF<(A, FixList)> -> A`
Keeping the original	Shared reference (GC)	`.clone()` required
`tails` implementation	Natural, no overhead	Same logic, clone cost per node
vs catamorphism	Only result visible	Result and original both visible
Performance	GC handles sharing	Clone copies subtrees — trade-off

// Example 220: Paramorphism — Cata with Access to Original Subtree

#[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)) }
    }
    fn map_ref<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 cata<A>(alg: &dyn Fn(ListF<A>) -> A, FixList(f): &FixList) -> A {
    alg(f.map_ref(|child| cata(alg, child)))
}

fn to_vec(fl: &FixList) -> Vec<i64> {
    cata(&|l| match l {
        ListF::NilF => vec![],
        ListF::ConsF(x, mut acc) => { acc.insert(0, x); acc }
    }, fl)
}

// para: algebra gets (result, original_subtree) for each child
fn para<A: Clone>(alg: &dyn Fn(ListF<(A, FixList)>) -> A, fl: &FixList) -> A {
    let paired = fl.0.map_ref(|child| (para(alg, child), child.clone()));
    alg(paired)
}

// Approach 1: tails — needs original subtree to convert
fn tails(fl: &FixList) -> Vec<Vec<i64>> {
    // Simple recursive implementation using para
    // tails [1,2] = [[1,2], [2], []]
    let full = to_vec(fl);
    let mut result = vec![full];
    let sub_tails = para(&|l: ListF<(Vec<Vec<i64>>, FixList)>| match l {
        ListF::NilF => vec![],
        ListF::ConsF(_, (rest_tails, original_tail)) => {
            let mut v = vec![to_vec(&original_tail)];
            v.extend(rest_tails);
            v
        }
    }, fl);
    result.extend(sub_tails);
    result
}

// Approach 2: Sliding window
fn sliding_window(n: usize, fl: &FixList) -> Vec<Vec<i64>> {
    para(&|l: ListF<(Vec<Vec<i64>>, FixList)>| match l {
        ListF::NilF => vec![],
        ListF::ConsF(x, (rest_windows, original_tail)) => {
            let mut remainder = vec![x];
            remainder.extend(to_vec(&original_tail));
            let mut result = if remainder.len() >= n {
                vec![remainder[..n].to_vec()]
            } else {
                vec![]
            };
            result.extend(rest_windows);
            result
        }
    }, fl)
}

// Approach 3: drop_while
fn drop_while(pred: impl Fn(i64) -> bool, fl: &FixList) -> Vec<i64> {
    para(&|l: ListF<(Vec<i64>, FixList)>| match l {
        ListF::NilF => vec![],
        ListF::ConsF(x, (rest, original_tail)) => {
            if pred(x) { rest }
            else { let mut v = vec![x]; v.extend(to_vec(&original_tail)); v }
        }
    }, fl)
}

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

    #[test]
    fn test_tails() {
        let xs = cons(1, cons(2, nil()));
        assert_eq!(tails(&xs), vec![vec![1,2], vec![2], vec![]]);
    }

    #[test]
    fn test_sliding() {
        let xs = cons(1, cons(2, cons(3, cons(4, nil()))));
        assert_eq!(sliding_window(3, &xs), vec![vec![1,2,3], vec![2,3,4]]);
    }

    #[test]
    fn test_drop_while_all() {
        let xs = cons(1, cons(2, nil()));
        assert_eq!(drop_while(|_| true, &xs), vec![]);
    }
}

(* Example 220: Paramorphism — Cata with Access to Original Subtree *)

(* para : ('f ('a * fix) -> 'a) -> fix -> 'a
   Like cata, but the algebra also sees the original subtree (not just the result). *)

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 unfix (FixL f) = f

let rec cata alg (FixL f) = alg (map_f (cata alg) f)

(* para: each position gets (result, original_subtree) *)
let rec para alg (FixL f as original) =
  let paired = map_f (fun child -> (para alg child, child)) f in
  alg paired

(* Approach 1: Factorial — para sees (n-1)! AND the original list from n-1 down *)
let nil = FixL NilF
let cons x xs = FixL (ConsF (x, xs))

let to_list fl = cata (function NilF -> [] | ConsF (x, acc) -> x :: acc) fl

(* Approach 2: tails — needs the original subtree *)
(* tails [1;2;3] = [[1;2;3]; [2;3]; [3]; []] *)
let tails_alg = function
  | NilF -> [[]]
  | ConsF (_, (rest_tails, original_tail)) ->
    to_list original_tail :: rest_tails
(* We need original_tail (the fix structure) to convert it to a list *)

let tails fl = (to_list fl) :: para tails_alg fl

(* Approach 3: Sliding window — needs access to remainder *)
let sliding_window_alg n = function
  | NilF -> []
  | ConsF (x, (rest_windows, original_tail)) ->
    let remainder = x :: to_list original_tail in
    if List.length remainder >= n then
      (List.filteri (fun i _ -> i < n) remainder) :: rest_windows
    else
      rest_windows

let sliding_window n fl = para (sliding_window_alg n) fl

(* Approach 4: Drop while — needs to know "am I still dropping?" *)
(* Actually simpler: suffix extraction *)
let drop_while_alg pred = function
  | NilF -> []
  | ConsF (x, (rest, original_tail)) ->
    if pred x then rest
    else x :: to_list original_tail

let drop_while pred fl = para (drop_while_alg pred) fl

(* === Tests === *)
let () =
  let xs = cons 1 (cons 2 (cons 3 nil)) in

  (* tails *)
  let t = tails xs in
  assert (t = [[1; 2; 3]; [2; 3]; [3]; []]);

  (* sliding window of size 2 *)
  let w = sliding_window 2 xs in
  assert (w = [[1; 2]; [2; 3]]);

  (* sliding window of size 3 *)
  let w3 = sliding_window 3 xs in
  assert (w3 = [[1; 2; 3]]);

  (* drop_while *)
  let xs2 = cons 1 (cons 2 (cons 3 (cons 1 nil))) in
  let d = drop_while (fun x -> x < 3) xs2 in
  assert (d = [3; 1]);

  let d2 = drop_while (fun _ -> false) xs in
  assert (d2 = [1; 2; 3]);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 220 — Paramorphism

para Definition

OCaml

🐪 Show OCaml equivalent

let rec para alg (FixL f as original) =
let paired = map_f (fun child -> (para alg child, child)) f in
alg paired

Rust

fn para<A: Clone>(alg: &dyn Fn(ListF<(A, FixList)>) -> A, fl: &FixList) -> A {
 let paired = fl.0.map_ref(|child| (para(alg, child), child.clone()));
 alg(paired)
}

tails Algebra

OCaml

🐪 Show OCaml equivalent

let tails_alg = function
| NilF -> [[]]
| ConsF (_, (rest_tails, original_tail)) ->
 to_list original_tail :: rest_tails

Rust

ListF::NilF => vec![vec![]],
ListF::ConsF(_, (rest_tails, original_tail)) => {
 let mut v = vec![to_vec(&original_tail)];
 v.extend(rest_tails);
 v
}

220: Paramorphism

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 220 — Paramorphism

para Definition

OCaml

Rust

tails Algebra

OCaml

Rust

Related Examples