607: Fixed-Point Types and Recursion Schemes

Difficulty: 5 Level: Master Express recursive types as `Fix<F>` — the fixed point of a functor — to get catamorphism, anamorphism, and hylomorphism for free.

The Problem This Solves

Every time you define a recursive type (`List`, `Tree`, `Expr`), you end up writing the same fold and unfold patterns from scratch. A tree fold and a list fold look structurally identical — but there's no abstraction that captures both without duplicating the recursion logic. The root cause is that recursive types bake recursion into their definition: `enum List<A> { Nil, Cons(A, Box<List<A>>) }`. What if you separated the "shape" of the type from the "recursion" itself? Define a non-recursive base functor `ListF<A, R>` where `R` is a placeholder for the recursive position. Then `Fix<ListF<A>>` is the recursive type. This separation is the key insight of recursion schemes: write your algebra once (`T → A`), apply `cata` to get a fold over any `Fix<F>` type. The recursive plumbing (traverse the structure, apply the algebra) is shared across all types. `Fix` is not academic — it's the formal basis for `serde`, AST transformations, and any library that needs generic traversal.

The Intuition

`Fix<F>` is the type where `Fix<F> = F<Fix<F>>` — it's the type that equals its own functor application, which is exactly what a recursive type is. The payoff: define your type as a non-recursive functor `F`, and you get `cata` (fold) and `ana` (unfold) for free, without re-implementing the recursion each time.

How It Works in Rust

// The fixed-point wrapper — wraps one layer of F
struct Fix<F: Functor>(Box<F::Applied<Fix<F>>>);

// A trait for types that can map their recursive position
trait Functor {
 type Applied<T>;
 fn fmap<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> B) -> Self::Applied<B>;
}

// Base functor for List<A> — R is the recursive position
enum ListF<A, R> {
 Nil,
 Cons(A, R),
}

// Manual Fixed-point for List — simplified (Rust GATs make this easier in nightly)
enum ListFix<A> {
 Nil,
 Cons(A, Box<ListFix<A>>),  // in practice: Fix<ListF<A>>
}

impl<A> ListFix<A> {
 // Catamorphism: fold using an algebra (ListF<A, B> → B)
 fn cata<B>(self, alg: &impl Fn(Option<(A, B)>) -> B) -> B {
     match self {
         ListFix::Nil        => alg(None),
         ListFix::Cons(a, t) => {
             let tb = t.cata(alg);   // recurse first — bottom-up
             alg(Some((a, tb)))       // then apply algebra
         }
     }
 }
}

// Using cata — algebra defines the computation, recursion is handled by cata
let list = ListFix::Cons(1, Box::new(ListFix::Cons(2, Box::new(ListFix::Nil))));
let sum = list.cata(&|node| match node {
 None        => 0,
 Some((a, b)) => a + b,
});

What This Unlocks

Generic traversals: write `cata` once per type; all folds share the structure.
Anamorphisms (`ana`): the dual — unfold a seed value into a recursive structure.
Hylomorphisms (`hylo = cata . ana`): build and immediately fold — fuses two traversals into one without intermediate allocation.

Key Differences

Concept	OCaml	Rust
Fixed point	`type 'f fix = Fix of 'f fix 'f`	`struct Fix<F>(Box<F::Applied<Fix<F>>>)`
Base functor	Type parameter in functor	`trait Functor` with `type Applied<T>`
Recursive position	Type variable	GAT `Applied<T>` (stable since 1.65)
`cata`	`let rec cata alg = function ...`	Method on `Fix<F>` or free function
Boxing overhead	GC-managed	`Box<T>` — one heap alloc per node
Practical use	`ppx_deriving` can generate folds	Manual or via `recursion` crate

// Base functor for a simple Nat type
#[derive(Debug)]
enum NatF<A> { Zero, Succ(A) }

// Fix: wraps the recursive layer in a Box
struct Fix<F>(Box<F>);

type Nat = Fix<NatF<Fix<NatF<()>>>>;  // Only 2 levels for demo; true Fix requires GAT/recursive types

// More practical: define recursion schemes over concrete types

// Expression base functor (non-recursive)
#[derive(Debug,Clone)]
enum ExprF<R> {
    Lit(i64),
    Add(R, R),
    Mul(R, R),
    Neg(R),
}

// Recursive expression using Fix-like structure
#[derive(Debug,Clone)]
struct Expr(Box<ExprF<Expr>>);

impl Expr {
    fn lit(n: i64) -> Self { Expr(Box::new(ExprF::Lit(n))) }
    fn add(l: Self, r: Self) -> Self { Expr(Box::new(ExprF::Add(l, r))) }
    fn mul(l: Self, r: Self) -> Self { Expr(Box::new(ExprF::Mul(l, r))) }
    fn neg(x: Self) -> Self { Expr(Box::new(ExprF::Neg(x))) }
}

// Catamorphism (fold) over the expression
fn cata<R>(expr: Expr, alg: &impl Fn(ExprF<R>) -> R) -> R {
    match *expr.0 {
        ExprF::Lit(n)    => alg(ExprF::Lit(n)),
        ExprF::Add(l,r)  => { let l=cata(l,alg); let r=cata(r,alg); alg(ExprF::Add(l,r)) }
        ExprF::Mul(l,r)  => { let l=cata(l,alg); let r=cata(r,alg); alg(ExprF::Mul(l,r)) }
        ExprF::Neg(x)    => { let x=cata(x,alg); alg(ExprF::Neg(x)) }
    }
}

// Two algebras
fn eval_alg(e: ExprF<i64>) -> i64 {
    match e { ExprF::Lit(n)=>n, ExprF::Add(l,r)=>l+r, ExprF::Mul(l,r)=>l*r, ExprF::Neg(x)=>-x }
}

fn print_alg(e: ExprF<String>) -> String {
    match e {
        ExprF::Lit(n)    => format!("{}", n),
        ExprF::Add(l,r)  => format!("({}+{})",l,r),
        ExprF::Mul(l,r)  => format!("({}*{})",l,r),
        ExprF::Neg(x)    => format!("(-{})",x),
    }
}

fn main() {
    // (3*4) + (-2)
    let e = Expr::add(
        Expr::mul(Expr::lit(3), Expr::lit(4)),
        Expr::neg(Expr::lit(2)),
    );
    let e2 = e.clone();
    println!("eval  = {}", cata(e,  &eval_alg));
    println!("print = {}", cata(e2, &print_alg));
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn eval_lit() { let e=Expr::lit(42); assert_eq!(cata(e,&eval_alg),42); }
    #[test] fn eval_add() { let e=Expr::add(Expr::lit(2),Expr::lit(3)); assert_eq!(cata(e,&eval_alg),5); }
}

(* Fixed-point types in OCaml *)

(* Fix-point of a functor *)
type 'f fix = Fix of ('f fix) 'f [@@unboxed]

(* Base functor for Nat *)
type 'a nat_f = Zero | Succ of 'a

(* Fix Nat *)
type nat = nat_f fix

let zero     = Fix Zero
let succ n   = Fix (Succ n)

let to_int (Fix n) =
  let rec go acc = function
    | Zero   -> acc
    | Succ (Fix n) -> go (acc+1) n
  in go 0 n

let () =
  let three = succ (succ (succ zero)) in
  Printf.printf "three = %d\n" (to_int three)