🎬 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

216: Fix Point — How Recursive Types Work Under the Hood

Difficulty: ⭐⭐⭐ Category: Recursion Schemes A single generic wrapper that turns any non-recursive shape into a fully recursive data structure.

The Problem This Solves

When you define a recursive type in Rust, the recursion and the shape are bundled together:

enum List {
 Nil,
 Cons(i64, Box<List>),  // shape AND recursion in one definition
}

This works fine until you want to write generic code over any recursive structure. Say you want one fold function that works for lists, trees, expressions, and anything else you might define. You can't — the recursion is baked into each type separately. What you really want to do is separate the two concerns: 1. The shape — what a single node looks like (its variant names and payload types) 2. The recursion — how nodes contain other nodes If you can separate these, you can write one `cata` (fold) function that works for any structure by parameterizing over the shape. You'd also be able to swap in different types for the "child" slot — put `i64` there and children become computed values; put `String` and they become rendered text; put the structure itself and you get full recursion. The fix point is the bridge: it's the generic wrapper that takes a non-recursive shape and makes it recursive. Every recursive type you've ever written can be seen as `Fix<SomeShape>`.

The Intuition

The word "fixed point" comes from math (don't panic): a fixed point of a function `f` is a value `x` where `f(x) = x`. That is, applying `f` doesn't change it. In types: the fix point of a type constructor `F` is a type `T` where `T = F<T>`. A type that equals itself when you plug it into `F`. Concretely — a linked list is a type `T` where `T = either Nil or (i64, T)`. That IS the definition of `List`. So `List` is the fixed point of `ListF`, where `ListF<A>` is "either Nil or (i64, A)". In Rust we write this literally:

// The shape — one node, children are generic A
enum ListF<A> {
 NilF,
 ConsF(i64, A),
}

// The fixed point — wraps itself: Fix contains ListF<Fix>
struct FixList(Box<ListF<FixList>>);
//                        ^^^^^
//                        children ARE FixList — full recursion restored

Think of `FixList` as a Russian doll: the outermost doll IS the structure, and when you open it (`unfix`), you find `ListF<FixList>` — the same type of doll inside. Dolls all the way down, until you hit `NilF` (no child doll).

How It Works in Rust

Step 1: Define the shape (non-recursive functor) Take any recursive type and replace all recursive children with `A`:

// ListF: shape of a list node. A = "what goes in the child position"
enum ListF<A> {
 NilF,           // the end — no child
 ConsF(i64, A),  // a value plus one child
}

// TreeF: shape of a binary tree node
enum TreeF<A> {
 LeafF(i64),    // leaf — no children
 BranchF(A, A), // two children
}

Step 2: Add `map` — transforms children This is required for `cata` to work. It applies a function to every child:

impl<A> ListF<A> {
 // Apply f to every child — NilF has none, ConsF has one
 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)),
     }
 }
}

Step 3: Create the fixed point wrapper

// FixList IS a ListF<FixList> — the type equation T = ListF<T> solved
struct FixList(Box<ListF<FixList>>);

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

// Usage: same as a normal linked list
let xs = cons(1, cons(2, cons(3, nil())));

Step 4: Write `cata` — the universal fold Once you have a fix point, `cata` is always the same pattern:

fn cata_list<A>(alg: &dyn Fn(ListF<A>) -> A, fix: &FixList) -> A {
 // 1. Get the node: fix.0 is a ListF<FixList>
 // 2. map_ref recursively evaluates all children first
 // 3. Now we have a ListF<A> — children already computed
 // 4. Pass it to the algebra to produce the final A
 alg(fix.0.map_ref(|child| cata_list(alg, child)))
}

Step 5: Write algebras — pure logic, no recursion

// Sum all elements
let sum_alg = |l: ListF<i64>| match l {
 ListF::NilF        => 0,         // empty: 0
 ListF::ConsF(x, a) => x + a,     // x + (already-summed tail)
};
assert_eq!(cata_list(&sum_alg, &xs), 6);

// Count elements
let len_alg = |l: ListF<usize>| match l {
 ListF::NilF        => 0,
 ListF::ConsF(_, a) => 1 + a,
};
assert_eq!(cata_list(&len_alg, &xs), 3);

The exact same pattern works for trees:

struct FixTree(Box<TreeF<FixTree>>);

fn leaf(n: i64) -> FixTree { FixTree(Box::new(TreeF::LeafF(n))) }
fn branch(l: FixTree, r: FixTree) -> FixTree { FixTree(Box::new(TreeF::BranchF(l, r))) }

fn cata_tree<A>(alg: &dyn Fn(TreeF<A>) -> A, fix: &FixTree) -> A {
 alg(fix.0.map_ref(|child| cata_tree(alg, child)))
}

let tree = branch(branch(leaf(1), leaf(2)), leaf(3));
let sum_tree = |t: TreeF<i64>| match t {
 TreeF::LeafF(n)      => n,
 TreeF::BranchF(l, r) => l + r,
};
assert_eq!(cata_tree(&sum_tree, &tree), 6);

Notice: the `cata` functions for lists and trees are structurally identical. The fix point is what makes this uniformity possible.

What This Unlocks

Generic recursion-scheme machinery. Once you have `Fix<F>` and `map` for your functor `F`, you get `cata` (fold), `ana` (unfold), and `hylo` (build-then-fold) for free — no per-type implementation needed.
Separate shape from recursion. You can test your node shape with simple `A` values before worrying about the recursive structure.
Foundation for compilers and interpreters. Real-world tools like expression evaluators, query optimizers, and AST transformers use this pattern — often without calling it by name.

Key Differences

Concept	OCaml	Rust
Fix type	`type 'a fix = In of 'a fix` or a module functor	`struct FixList(Box<ListF<FixList>>)` — one per shape
Box requirement	Not needed (GC manages heap)	Required — Rust needs explicit heap allocation for recursive types
Generic fix	Single `Fix` type via module functors	Separate `FixList`, `FixTree`, etc. (GATs can generalize this)
Functor map	Standalone function, usually polymorphic	Method on the concrete enum
Unfix	`let (In f) = x` pattern	`fix.0` or custom `unfix()` method

// Example 216: Fix Point — Unrolling Recursion from a Functor

// Approach 1: Fix point for lists
#[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, rest) => ListF::ConsF(x, f(rest)),
        }
    }
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> ListF<B> {
        match self {
            ListF::NilF => ListF::NilF,
            ListF::ConsF(x, rest) => ListF::ConsF(*x, f(rest)),
        }
    }
}

#[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_list<A>(alg: &dyn Fn(ListF<A>) -> A, fix: &FixList) -> A {
    alg(fix.0.map_ref(|child| cata_list(alg, child)))
}

// Approach 2: Fix point for binary trees
#[derive(Debug, Clone)]
enum TreeF<A> {
    LeafF(i64),
    BranchF(A, A),
}

impl<A> TreeF<A> {
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> TreeF<B> {
        match self {
            TreeF::LeafF(n) => TreeF::LeafF(*n),
            TreeF::BranchF(l, r) => TreeF::BranchF(f(l), f(r)),
        }
    }
}

#[derive(Debug, Clone)]
struct FixTree(Box<TreeF<FixTree>>);

fn leaf(n: i64) -> FixTree { FixTree(Box::new(TreeF::LeafF(n))) }
fn branch(l: FixTree, r: FixTree) -> FixTree { FixTree(Box::new(TreeF::BranchF(l, r))) }

fn cata_tree<A>(alg: &dyn Fn(TreeF<A>) -> A, fix: &FixTree) -> A {
    alg(fix.0.map_ref(|child| cata_tree(alg, child)))
}

// Approach 3: Generic Fix via trait
trait Functor: Sized {
    type Inner;
    fn fmap<B>(&self, f: impl Fn(&Self::Inner) -> B) -> Self::Mapped<B>;
    type Mapped<B>;
}

fn main() {
    // List fix point
    let xs = cons(1, cons(2, cons(3, nil())));

    let sum_alg = |l: ListF<i64>| match l {
        ListF::NilF => 0,
        ListF::ConsF(x, acc) => x + acc,
    };
    assert_eq!(cata_list(&sum_alg, &xs), 6);

    let len_alg = |l: ListF<usize>| match l {
        ListF::NilF => 0,
        ListF::ConsF(_, acc) => 1 + acc,
    };
    assert_eq!(cata_list(&len_alg, &xs), 3);

    let to_vec = |l: ListF<Vec<i64>>| match l {
        ListF::NilF => vec![],
        ListF::ConsF(x, mut acc) => { acc.insert(0, x); acc },
    };
    assert_eq!(cata_list(&to_vec, &xs), vec![1, 2, 3]);

    // Tree fix point
    let tree = branch(branch(leaf(1), leaf(2)), leaf(3));

    let sum_tree = |t: TreeF<i64>| match t {
        TreeF::LeafF(n) => n,
        TreeF::BranchF(l, r) => l + r,
    };
    assert_eq!(cata_tree(&sum_tree, &tree), 6);

    let depth_tree = |t: TreeF<usize>| match t {
        TreeF::LeafF(_) => 0,
        TreeF::BranchF(l, r) => 1 + l.max(r),
    };
    assert_eq!(cata_tree(&depth_tree, &tree), 2);

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

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

    #[test]
    fn test_list_cata() {
        let xs = cons(10, cons(20, nil()));
        let sum = |l: ListF<i64>| match l { ListF::NilF => 0, ListF::ConsF(x, a) => x + a };
        assert_eq!(cata_list(&sum, &xs), 30);
    }

    #[test]
    fn test_empty_list() {
        let sum = |l: ListF<i64>| match l { ListF::NilF => 0, ListF::ConsF(x, a) => x + a };
        assert_eq!(cata_list(&sum, &nil()), 0);
    }

    #[test]
    fn test_tree_count() {
        let t = branch(leaf(1), branch(leaf(2), leaf(3)));
        let count = |t: TreeF<usize>| match t { TreeF::LeafF(_) => 1, TreeF::BranchF(l, r) => l + r };
        assert_eq!(cata_tree(&count, &t), 3);
    }
}

(* Example 216: Fix Point — Unrolling Recursion from a Functor *)

(* The key insight: separate the SHAPE of data from RECURSION itself.
   type 'a list_f = NilF | ConsF of int * 'a    (* one layer, non-recursive *)
   type fix_list = fix_list list_f               (* recursion via fix point *)
*)

(* Approach 1: Fix point for lists *)
type 'a list_f = NilF | ConsF of int * 'a

let map_list_f f = function
  | NilF -> NilF
  | ConsF (x, rest) -> ConsF (x, f rest)

type fix_list = FixL of fix_list list_f

let unfix_l (FixL f) = f

(* Build lists *)
let nil = FixL NilF
let cons x xs = FixL (ConsF (x, xs))

(* cata for lists *)
let rec cata_list alg (FixL f) =
  alg (map_list_f (cata_list alg) f)

(* Approach 2: Fix point for binary trees *)
type 'a tree_f = LeafF of int | BranchF of 'a * 'a

let map_tree_f f = function
  | LeafF n -> LeafF n
  | BranchF (l, r) -> BranchF (f l, f r)

type fix_tree = FixT of fix_tree tree_f

let unfix_t (FixT f) = f

let leaf n = FixT (LeafF n)
let branch l r = FixT (BranchF (l, r))

let rec cata_tree alg (FixT f) =
  alg (map_tree_f (cata_tree alg) f)

(* Approach 3: Generic fix point (using polymorphic variant or functor) *)
(* In OCaml, we can use a functor module *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module Fix (F : FUNCTOR) = struct
  type t = In of t F.t
  let out (In f) = f
  let rec cata alg (In f) =
    alg (F.map (cata alg) f)
end

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

  let sum_alg = function NilF -> 0 | ConsF (x, acc) -> x + acc in
  assert (cata_list sum_alg xs = 6);

  let length_alg = function NilF -> 0 | ConsF (_, acc) -> 1 + acc in
  assert (cata_list length_alg xs = 3);

  let to_list_alg = function NilF -> [] | ConsF (x, acc) -> x :: acc in
  assert (cata_list to_list_alg xs = [1; 2; 3]);

  (* Tree fix point *)
  let tree = branch (branch (leaf 1) (leaf 2)) (leaf 3) in

  let sum_tree = function LeafF n -> n | BranchF (l, r) -> l + r in
  assert (cata_tree sum_tree tree = 6);

  let depth_tree = function LeafF _ -> 0 | BranchF (l, r) -> 1 + max l r in
  assert (cata_tree depth_tree tree = 2);

  let count_tree = function LeafF _ -> 1 | BranchF (l, r) -> l + r in
  assert (cata_tree count_tree tree = 3);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 216 — Fix Point

Non-Recursive Functor

OCaml

🐪 Show OCaml equivalent

type 'a list_f = NilF | ConsF of int * 'a
let map_list_f f = function
| NilF -> NilF
| ConsF (x, rest) -> ConsF (x, f rest)

Rust

enum ListF<A> { NilF, ConsF(i64, A) }
impl<A> ListF<A> {
 fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> ListF<B> {
     match self {
         ListF::NilF => ListF::NilF,
         ListF::ConsF(x, rest) => ListF::ConsF(*x, f(rest)),
     }
 }
}

Fix Point + cata

OCaml

🐪 Show OCaml equivalent

type fix_list = FixL of fix_list list_f
let rec cata_list alg (FixL f) =
alg (map_list_f (cata_list alg) f)

Rust

struct FixList(Box<ListF<FixList>>);
fn cata_list<A>(alg: &dyn Fn(ListF<A>) -> A, fix: &FixList) -> A {
 alg(fix.0.map_ref(|child| cata_list(alg, child)))
}

Using an Algebra

OCaml

🐪 Show OCaml equivalent

let sum_alg = function NilF -> 0 | ConsF (x, acc) -> x + acc
let total = cata_list sum_alg my_list

Rust

let sum_alg = |l: ListF<i64>| match l {
 ListF::NilF => 0, ListF::ConsF(x, acc) => x + acc,
};
let total = cata_list(&sum_alg, &my_list);

216: Fix Point — How Recursive Types Work Under the Hood

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 216 — Fix Point

Non-Recursive Functor

OCaml

Rust

Fix Point + cata

OCaml

Rust

Using an Algebra

OCaml

Rust

Related Examples