🎬 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

224: Mutumorphism

Difficulty: 5 Level: Expert Two folds that depend on each other — compute two results simultaneously where each depends on the other's intermediate values.

The Problem This Solves

Zygo (example 221) runs one "helper" fold alongside a main fold, but the helper is independent — the main fold uses helper results, not vice versa. Mutumorphism is genuinely mutual: both folds receive each other's results at every step. The canonical example: `isEven` and `isOdd` are mutually recursive by definition — `isEven(n) = isOdd(n-1)` and `isOdd(n) = isEven(n-1)`. You can't compute one without the other. Mutumorphism encodes this as two algebras that receive a paired `(A, B)` layer. A more compelling use case: simultaneously evaluate an expression and type-check it. Both the value and the type of each subexpression are needed to compute the value and type of the parent.

The Intuition

In `mutu(alg_a, alg_b, tree)`, both algebras receive `F<(A, B)>` — the functor layer where each recursive position has already been expanded into the pair of both results. Each algebra picks what it needs from the pair. Compare to `cata`: `cata(alg, tree)` gives `alg` an `F<A>` — just one result per position. `mutu` gives both algebras an `F<(A, B)>` — the full pair at every position. This is why `isEven` can call `isOdd` at each step without a separate traversal. The result is a pair `(A, B)` produced in a single pass, even though both sides depend on each other.

How It Works in Rust

fn mutu<A: Clone, B: Clone>(
 alg_a: &dyn Fn(NatF<(A, B)>) -> A,   // sees BOTH results at each position
 alg_b: &dyn Fn(NatF<(A, B)>) -> B,
 fix: &FixNat,
) -> (A, B) {
 // Recursively expand each child into its (A, B) pair
 let paired: NatF<(A, B)> = fix.0.map_ref(|child| mutu(alg_a, alg_b, child));
 // Both algebras receive the same paired layer — must clone to share
 (alg_a(paired.clone()), alg_b(paired))
}

isEven / isOdd — the mutual dependency in action:

fn is_even_alg(n: NatF<(bool, bool)>) -> bool {
 match n {
     NatF::ZeroF => true,                  // 0 is even
     NatF::SuccF((_even, odd)) => odd,     // n+1 is even iff n is odd
 }
}

fn is_odd_alg(n: NatF<(bool, bool)>) -> bool {
 match n {
     NatF::ZeroF => false,                 // 0 is not odd
     NatF::SuccF((even, _odd)) => even,    // n+1 is odd iff n is even
 }
}

// Both computed in a single traversal:
let (even, odd) = mutu(&is_even_alg, &is_odd_alg, &nat(4));
// even = true, odd = false

Simultaneous evaluation + type-checking:

fn val_alg(e: ExprF<(Value, Typ)>) -> Value {
 match e {
     ExprF::Add((Value::VInt(a), _), (Value::VInt(b), _)) => Value::VInt(a + b),
     ExprF::If((Value::VBool(true), _), (v, _), _) => v,  // use type to guide eval
     _ => Value::VError,
 }
}

fn typ_alg(e: ExprF<(Value, Typ)>) -> Typ {
 match e {
     ExprF::Add((_, Typ::TInt), (_, Typ::TInt)) => Typ::TInt,
     ExprF::If((_, Typ::TBool), (_, t1), (_, t2)) if t1 == t2 => t1,
     _ => Typ::TError,
 }
}

// Type and value computed together — one pass, mutual dependency
let (value, typ) = mutu_expr(&val_alg, &typ_alg, &expr);

What This Unlocks

Simultaneous evaluation + type-checking — one traversal instead of two separate passes
Even/odd parity tracking — any mutually-defined predicate on recursive structures
Co-dependent accumulations — wherever two summary values at a node depend on each other's child values

Key Differences

Concept	OCaml	Rust
Algebra signature	`'f ('a 'b) -> 'a`	`Fn(F<(A, B)>) -> A`
Pair type	`'a 'b` (native tuple)	`(A, B)`
Layer sharing	Single evaluation, GC handles aliasing	`.clone()` required to share paired layer between two algebras
Pattern matching	`VInt a, _` on pair	`(Value::VInt(a), _)` — same structure
vs zygo	Helper is one-way dependency	Both algebras are mutually dependent

// Example 224: Mutumorphism — Genuinely Mutual Recursion

// mutu: two folds that depend on EACH OTHER

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

impl<A> NatF<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)) }
    }
}

#[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)) }

fn mutu<A: Clone, B: Clone>(
    alg_a: &dyn Fn(NatF<(A, B)>) -> A,
    alg_b: &dyn Fn(NatF<(A, B)>) -> B,
    fix: &FixNat,
) -> (A, B) {
    let paired = fix.0.map_ref(|child| mutu(alg_a, alg_b, child));
    (alg_a(paired.clone()), alg_b(paired))
}

impl<A: Clone> Clone for NatF<A> {
    fn clone(&self) -> Self { self.map_ref(|a| a.clone()) }
}

// Approach 1: isEven / isOdd
fn is_even_alg(n: NatF<(bool, bool)>) -> bool {
    match n { NatF::ZeroF => true, NatF::SuccF((_even, odd)) => odd }
}

fn is_odd_alg(n: NatF<(bool, bool)>) -> bool {
    match n { NatF::ZeroF => false, NatF::SuccF((even, _odd)) => even }
}

fn is_even(n: u32) -> bool { mutu(&is_even_alg, &is_odd_alg, &nat(n)).0 }
fn is_odd(n: u32) -> bool { mutu(&is_even_alg, &is_odd_alg, &nat(n)).1 }

// Approach 2: Typed expression evaluation — value AND type simultaneously
#[derive(Debug, PartialEq)]
enum ExprF<A> { IntLit(i64), BoolLit(bool), Add(A, A), Eq(A, A), If(A, A, A) }

impl<A> ExprF<A> {
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> ExprF<B> {
        match self {
            ExprF::IntLit(n) => ExprF::IntLit(*n),
            ExprF::BoolLit(b) => ExprF::BoolLit(*b),
            ExprF::Add(a, b) => ExprF::Add(f(a), f(b)),
            ExprF::Eq(a, b) => ExprF::Eq(f(a), f(b)),
            ExprF::If(c, t, e) => ExprF::If(f(c), f(t), f(e)),
        }
    }
}

impl<A: Clone> Clone for ExprF<A> {
    fn clone(&self) -> Self { self.map_ref(|a| a.clone()) }
}

#[derive(Debug, Clone)]
struct FixExpr(Box<ExprF<FixExpr>>);

#[derive(Debug, Clone, PartialEq)]
enum Value { VInt(i64), VBool(bool), VError }

#[derive(Debug, Clone, PartialEq)]
enum Typ { TInt, TBool, TError }

fn mutu_expr<A: Clone, B: Clone>(
    alg_a: &dyn Fn(ExprF<(A, B)>) -> A,
    alg_b: &dyn Fn(ExprF<(A, B)>) -> B,
    fix: &FixExpr,
) -> (A, B) {
    let paired = fix.0.map_ref(|child| mutu_expr(alg_a, alg_b, child));
    (alg_a(paired.clone()), alg_b(paired))
}

fn val_alg(e: ExprF<(Value, Typ)>) -> Value {
    match e {
        ExprF::IntLit(n) => Value::VInt(n),
        ExprF::BoolLit(b) => Value::VBool(b),
        ExprF::Add((Value::VInt(a), _), (Value::VInt(b), _)) => Value::VInt(a + b),
        ExprF::Eq((Value::VInt(a), _), (Value::VInt(b), _)) => Value::VBool(a == b),
        ExprF::If((Value::VBool(true), _), (v, _), _) => v,
        ExprF::If((Value::VBool(false), _), _, (v, _)) => v,
        _ => Value::VError,
    }
}

fn typ_alg(e: ExprF<(Value, Typ)>) -> Typ {
    match e {
        ExprF::IntLit(_) => Typ::TInt,
        ExprF::BoolLit(_) => Typ::TBool,
        ExprF::Add((_, Typ::TInt), (_, Typ::TInt)) => Typ::TInt,
        ExprF::Eq((_, Typ::TInt), (_, Typ::TInt)) => Typ::TBool,
        ExprF::If((_, Typ::TBool), (_, t1), (_, t2)) if t1 == t2 => t1,
        _ => Typ::TError,
    }
}

fn int_lit(n: i64) -> FixExpr { FixExpr(Box::new(ExprF::IntLit(n))) }
fn bool_lit(b: bool) -> FixExpr { FixExpr(Box::new(ExprF::BoolLit(b))) }
fn add_e(a: FixExpr, b: FixExpr) -> FixExpr { FixExpr(Box::new(ExprF::Add(a, b))) }
fn eq_e(a: FixExpr, b: FixExpr) -> FixExpr { FixExpr(Box::new(ExprF::Eq(a, b))) }
fn if_e(c: FixExpr, t: FixExpr, e: FixExpr) -> FixExpr { FixExpr(Box::new(ExprF::If(c, t, e))) }

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

    #[test] fn test_even_odd() {
        for i in 0..10 { assert_eq!(is_even(i), i % 2 == 0); }
    }

    #[test] fn test_type_check_ok() {
        let e = eq_e(int_lit(1), int_lit(2));
        let (v, t) = mutu_expr(&val_alg, &typ_alg, &e);
        assert_eq!(v, Value::VBool(false));
        assert_eq!(t, Typ::TBool);
    }

    #[test] fn test_type_error() {
        let e = eq_e(int_lit(1), bool_lit(true));
        assert_eq!(mutu_expr(&val_alg, &typ_alg, &e).1, Typ::TError);
    }
}

(* Example 224: Mutumorphism — Genuinely Mutual Recursion *)

(* mutu : ('f ('a,'b) -> 'a) -> ('f ('a,'b) -> 'b) -> fix -> ('a, 'b)
   Two folds that depend on EACH OTHER. Unlike zygo where the helper is independent. *)

type 'a nat_f = ZeroF | SuccF of 'a

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

type fix_nat = FixN of fix_nat nat_f

(* Approach 1: isEven / isOdd — classic mutual recursion *)
(* isEven 0 = true,  isEven (n+1) = isOdd n
   isOdd 0  = false, isOdd  (n+1) = isEven n *)

let rec mutu alg_a alg_b (FixN f) =
  let paired = map_nat (mutu alg_a alg_b) f in
  (alg_a (map_nat fst paired), alg_b (map_nat snd paired))
(* Hmm, this maps twice. Better: *)

let rec mutu alg_a alg_b (FixN f) =
  let paired = map_nat (fun child -> mutu alg_a alg_b child) f in
  (alg_a paired, alg_b paired)
(* But paired has type (a*b) nat_f, and alg_a needs it too *)

(* Correct implementation *)
let rec mutu (alg_a : ('a * 'b) nat_f -> 'a) (alg_b : ('a * 'b) nat_f -> 'b) (FixN f : fix_nat) : ('a * 'b) =
  let paired = map_nat (mutu alg_a alg_b) f in
  (alg_a paired, alg_b paired)

let is_even_alg : (bool * bool) nat_f -> bool = function
  | ZeroF -> true
  | SuccF (_even, odd) -> odd  (* isEven(n+1) = isOdd(n) *)

let is_odd_alg : (bool * bool) nat_f -> bool = function
  | ZeroF -> false
  | SuccF (even, _odd) -> even  (* isOdd(n+1) = isEven(n) *)

let zero = FixN ZeroF
let succ n = FixN (SuccF n)
let rec nat n = if n <= 0 then zero else succ (nat (n - 1))

let is_even n = fst (mutu is_even_alg is_odd_alg (nat n))
let is_odd n = snd (mutu is_even_alg is_odd_alg (nat n))

(* Approach 2: Collatz conjecture — count steps AND track max *)
(* But with natural numbers: parity-check + step-count *)

(* Approach 3: Expression — compute value AND type simultaneously *)
type 'a expr_f =
  | IntLitF of int
  | BoolLitF of bool
  | AddF of 'a * 'a
  | EqF of 'a * 'a    (* equality check *)
  | IfF of 'a * 'a * 'a

let map_ef f = function
  | IntLitF n -> IntLitF n
  | BoolLitF b -> BoolLitF b
  | AddF (a, b) -> AddF (f a, f b)
  | EqF (a, b) -> EqF (f a, f b)
  | IfF (c, t, e) -> IfF (f c, f t, f e)

type fix_expr = FixE of fix_expr expr_f

type value = VInt of int | VBool of bool | VError
type typ = TInt | TBool | TError

let rec mutu_expr val_alg typ_alg (FixE f) =
  let paired = map_ef (mutu_expr val_alg typ_alg) f in
  (val_alg paired, typ_alg paired)

let val_alg : (value * typ) expr_f -> value = function
  | IntLitF n -> VInt n
  | BoolLitF b -> VBool b
  | AddF ((VInt a, _), (VInt b, _)) -> VInt (a + b)
  | EqF ((VInt a, _), (VInt b, _)) -> VBool (a = b)
  | IfF ((VBool true, _), (v, _), _) -> v
  | IfF ((VBool false, _), _, (v, _)) -> v
  | _ -> VError

let typ_alg : (value * typ) expr_f -> typ = function
  | IntLitF _ -> TInt
  | BoolLitF _ -> TBool
  | AddF ((_, TInt), (_, TInt)) -> TInt
  | EqF ((_, TInt), (_, TInt)) -> TBool
  | IfF ((_, TBool), (_, t1), (_, t2)) when t1 = t2 -> t1
  | _ -> TError

let int_lit n = FixE (IntLitF n)
let bool_lit b = FixE (BoolLitF b)
let add_e a b = FixE (AddF (a, b))
let eq_e a b = FixE (EqF (a, b))
let if_e c t e = FixE (IfF (c, t, e))

(* === Tests === *)
let () =
  (* Even/Odd *)
  assert (is_even 0 = true);
  assert (is_even 1 = false);
  assert (is_even 4 = true);
  assert (is_odd 3 = true);
  assert (is_odd 6 = false);

  (* Type-checking expression *)
  let e = add_e (int_lit 1) (int_lit 2) in
  let (v, t) = mutu_expr val_alg typ_alg e in
  assert (v = VInt 3);
  assert (t = TInt);

  let e2 = if_e (eq_e (int_lit 1) (int_lit 1)) (int_lit 42) (int_lit 0) in
  let (v2, t2) = mutu_expr val_alg typ_alg e2 in
  assert (v2 = VInt 42);
  assert (t2 = TInt);

  (* Type error *)
  let e3 = add_e (int_lit 1) (bool_lit true) in
  let (v3, t3) = mutu_expr val_alg typ_alg e3 in
  assert (v3 = VError);
  assert (t3 = TError);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 224 — Mutumorphism

mutu Definition

OCaml

🐪 Show OCaml equivalent

let rec mutu alg_a alg_b (FixN f) =
let paired = map_nat (mutu alg_a alg_b) f in
(alg_a paired, alg_b paired)

Rust

fn mutu<A: Clone, B: Clone>(
 alg_a: &dyn Fn(NatF<(A, B)>) -> A,
 alg_b: &dyn Fn(NatF<(A, B)>) -> B,
 fix: &FixNat,
) -> (A, B) {
 let paired = fix.0.map_ref(|child| mutu(alg_a, alg_b, child));
 (alg_a(paired.clone()), alg_b(paired))
}

isEven / isOdd

OCaml

🐪 Show OCaml equivalent

let is_even_alg = function
| ZeroF -> true
| SuccF (_even, odd) -> odd   (* isEven depends on isOdd *)

let is_odd_alg = function
| ZeroF -> false
| SuccF (even, _odd) -> even  (* isOdd depends on isEven *)

Rust

fn is_even_alg(n: NatF<(bool, bool)>) -> bool {
 match n { NatF::ZeroF => true, NatF::SuccF((_even, odd)) => odd }
}
fn is_odd_alg(n: NatF<(bool, bool)>) -> bool {
 match n { NatF::ZeroF => false, NatF::SuccF((even, _odd)) => even }
}

Typed Expression

OCaml

🐪 Show OCaml equivalent

let val_alg = function
| AddF ((VInt a, _), (VInt b, _)) -> VInt (a + b)
| IfF ((VBool true, _), (v, _), _) -> v
| _ -> VError

Rust

fn val_alg(e: ExprF<(Value, Typ)>) -> Value {
 match e {
     ExprF::Add((Value::VInt(a), _), (Value::VInt(b), _)) => Value::VInt(a + b),
     ExprF::If((Value::VBool(true), _), (v, _), _) => v,
     _ => Value::VError,
 }
}

224: Mutumorphism

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 224 — Mutumorphism

mutu Definition

OCaml

Rust

isEven / isOdd

OCaml

Rust

Typed Expression

OCaml

Rust

Related Examples