🎬 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

223: Zygomorphism

Difficulty: ⭐⭐⭐ Level: Recursion Schemes Run two fold algebras simultaneously in one pass, where the main algebra can see both its own results and the helper algebra's results at each step.

The Problem This Solves

Sometimes you need two things from one fold, and they're not independent — one depends on the other. Computing the average of a list in one pass requires both the sum and the count. But if you write two separate folds, you traverse the structure twice. And if you just pair up the results with a plain fold, the two computations can't see each other's intermediate values. Zygomorphism solves this: run a helper fold and a main fold simultaneously. The helper runs independently. The main fold sees its own accumulated values and the helper's values at every node. They share one traversal, and the main algebra gets the richer information it needs. The name comes from Greek zygo (yoke) — two computations yoked together, sharing the burden of a single traversal.

The Intuition

Picture a spreadsheet with two computed columns. Column B uses only the raw data. Column A uses both the raw data and column B's values. Zygomorphism computes both columns in one left-to-right pass. Classic example: pretty-printing an expression tree with correct precedence. The helper computes the numeric value (or precedence level) of each subexpression. The main printer uses those values to decide whether to add parentheses. Without zygomorphism, you'd traverse twice or thread awkward state. Another example: safety-checking a calculation. The helper evaluates the expression to get actual numbers. The main checker looks at those numbers to decide if any division-by-zero risk exists. The helper's intermediate evaluations guide the main checker's decisions. Algebra shapes:

Helper: `ExprF<B> -> B` — sees only helper results below it
Main: `ExprF<(A, B)> -> A` — sees (main_result, helper_result) pairs below it

How It Works in Rust

// zygo: compute (main_result, helper_result) simultaneously
fn zygo_both<A: Clone, B: Clone>(
 helper: &dyn Fn(ExprF<B>) -> B,      // independent helper fold
 main:   &dyn Fn(ExprF<(A, B)>) -> A, // main fold sees both
 fix: &Fix,
) -> (A, B) {
 // For each child: recurse to get (A, B) pair
 let paired: ExprF<(A, B)> = fix.0.map_ref(|child| zygo_both(helper, main, child));

 // Extract only B values for the helper
 let b_layer = paired.map_ref(|(_, b)| b.clone());

 // Run both algebras at this node
 let a = main(paired.clone());   // main sees (A, B) pairs
 let b = helper(b_layer);        // helper sees only B values
 (a, b)
}

Safety-check example — helper evaluates, main checks for danger:

// Helper: plain evaluator
fn eval_helper(e: ExprF<i64>) -> i64 {
 match e {
     ExprF::LitF(n)     => n,
     ExprF::AddF(a, b)  => a + b,
     ExprF::MulF(a, b)  => a * b,
     ExprF::NegF(a)     => -a,
 }
}

// Main: safety check — uses helper's computed values to detect overflow risk
fn safe_check(e: ExprF<(String, i64)>) -> String {
 match e {
     ExprF::LitF(n) => format!("safe({})", n),
     ExprF::AddF((sa, va), (sb, vb)) =>
         if va.saturating_add(vb) != va + vb {
             format!("OVERFLOW({} + {})", sa, sb)  // va available from helper!
         } else {
             format!("safe({} + {})", sa, sb)
         },
     // ...
 }
}

The main algebra uses `va` and `vb` — the helper's computed values — to make decisions a pure structural fold couldn't make.

What This Unlocks

One-pass average — helper computes `(sum, count)`, main formats the result. No second traversal.
Pretty-printing with precedence — helper computes precedence level, main uses it to decide parentheses. No separate precedence pass.
Validation + transformation — helper validates, main transforms using validation results. Errors and transformations interleaved in one pass.

Key Differences

Concept	OCaml	Rust
Helper algebra	`ExprF 'b -> 'b`	`ExprF<B> -> B`
Main algebra	`ExprF ('a * 'b) -> 'a`	`ExprF<(A, B)> -> A`
Pair extraction	`map_f snd`	`.map_ref(\	(_, b)\	b.clone())`
Clone overhead	None (GC)	Clone paired layer for split
vs two separate folds	Two traversals	One traversal, shared

// Example 223: Zygomorphism — Two Mutually Dependent Folds

#[derive(Debug, Clone)]
enum ExprF<A> { LitF(i64), AddF(A, A), MulF(A, A), NegF(A) }

impl<A> ExprF<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> ExprF<B> {
        match self {
            ExprF::LitF(n) => ExprF::LitF(n),
            ExprF::AddF(a, b) => ExprF::AddF(f(a), f(b)),
            ExprF::MulF(a, b) => ExprF::MulF(f(a), f(b)),
            ExprF::NegF(a) => ExprF::NegF(f(a)),
        }
    }
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> ExprF<B> {
        match self {
            ExprF::LitF(n) => ExprF::LitF(*n),
            ExprF::AddF(a, b) => ExprF::AddF(f(a), f(b)),
            ExprF::MulF(a, b) => ExprF::MulF(f(a), f(b)),
            ExprF::NegF(a) => ExprF::NegF(f(a)),
        }
    }
    fn map_snd<X, Y, B>(&self, f: impl Fn(&(X, Y)) -> B) -> ExprF<B>
    where A: AsRef<(X, Y)> {
        self.map_ref(|a| f(a.as_ref()))
    }
}

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

// zygo: compute (main_result, helper_result) simultaneously
fn zygo_both<A: Clone, B: Clone>(
    helper: &dyn Fn(ExprF<B>) -> B,
    main: &dyn Fn(ExprF<(A, B)>) -> A,
    fix: &Fix,
) -> (A, B) {
    let paired: ExprF<(A, B)> = fix.0.map_ref(|child| zygo_both(helper, main, child));
    let b_layer = paired.map_ref(|(_, b)| b.clone());
    let a = main(paired.clone());
    let b = helper(b_layer);
    (a, b)
}

fn zygo<A: Clone, B: Clone>(
    helper: &dyn Fn(ExprF<B>) -> B,
    main: &dyn Fn(ExprF<(A, B)>) -> A,
    fix: &Fix,
) -> A {
    zygo_both(helper, main, fix).0
}

// ExprF derives Clone, which covers ExprF<(A, B)> when A: Clone

// Approach 1: Safety check — helper evaluates, main checks bounds
fn eval_helper(e: ExprF<i64>) -> i64 {
    match e {
        ExprF::LitF(n) => n,
        ExprF::AddF(a, b) => a + b,
        ExprF::MulF(a, b) => a * b,
        ExprF::NegF(a) => -a,
    }
}

fn safe_main(e: ExprF<(bool, i64)>) -> bool {
    match e {
        ExprF::LitF(_) => true,
        ExprF::AddF((a, _), (b, _)) => a && b,
        ExprF::MulF((a, va), (b, vb)) => a && b && va.abs() < 1000 && vb.abs() < 1000,
        ExprF::NegF((a, _)) => a,
    }
}

// Approach 2: Pretty print with precedence
fn prec_helper(e: ExprF<u32>) -> u32 {
    match e {
        ExprF::LitF(_) => 100,
        ExprF::AddF(_, _) => 1,
        ExprF::MulF(_, _) => 2,
        ExprF::NegF(_) => 3,
    }
}

fn show_main(e: ExprF<(String, u32)>) -> String {
    match e {
        ExprF::LitF(n) => n.to_string(),
        ExprF::AddF((a, pa), (b, pb)) => {
            let la = if pa < 1 { format!("({a})") } else { a };
            let rb = if pb < 1 { format!("({b})") } else { b };
            format!("{la} + {rb}")
        }
        ExprF::MulF((a, pa), (b, pb)) => {
            let la = if pa < 2 { format!("({a})") } else { a };
            let rb = if pb < 2 { format!("({b})") } else { b };
            format!("{la} * {rb}")
        }
        ExprF::NegF((a, _)) => format!("-{a}"),
    }
}

fn lit(n: i64) -> Fix { Fix(Box::new(ExprF::LitF(n))) }
fn add(a: Fix, b: Fix) -> Fix { Fix(Box::new(ExprF::AddF(a, b))) }
fn mul(a: Fix, b: Fix) -> Fix { Fix(Box::new(ExprF::MulF(a, b))) }
fn neg(a: Fix) -> Fix { Fix(Box::new(ExprF::NegF(a))) }

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

    #[test]
    fn test_safe() {
        assert!(zygo(&eval_helper, &safe_main, &add(lit(1), lit(2))));
    }

    #[test]
    fn test_unsafe() {
        assert!(!zygo(&eval_helper, &safe_main, &mul(lit(100000), lit(2))));
    }

    #[test]
    fn test_precedence() {
        let e = add(mul(lit(2), lit(3)), lit(4));
        assert_eq!(zygo(&prec_helper, &show_main, &e), "2 * 3 + 4");
    }
}

(* Example 223: Zygomorphism — Two Mutually Dependent Folds *)

(* zygo : ('f 'b -> 'b) -> ('f ('a, 'b) -> 'a) -> fix -> 'a
   Run two folds simultaneously: the main fold sees both results,
   the helper fold runs independently. *)

type 'a expr_f =
  | LitF of int
  | AddF of 'a * 'a
  | MulF of 'a * 'a
  | NegF of 'a

let map_f f = function
  | LitF n -> LitF n
  | AddF (a, b) -> AddF (f a, f b)
  | MulF (a, b) -> MulF (f a, f b)
  | NegF a -> NegF (f a)

type fix = Fix of fix expr_f

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

(* zygo: helper fold computes 'b, main fold sees both 'a and 'b *)
let rec zygo helper_alg main_alg (Fix f) =
  let paired = map_f (fun child ->
    let a = zygo helper_alg main_alg child in
    let b = cata helper_alg child in
    (a, b)
  ) f in
  main_alg paired

(* More efficient: compute both in one pass *)
let rec zygo_eff helper main (Fix f) =
  let paired = map_f (fun child ->
    let (a, b) = zygo_both helper main child in
    (a, b)
  ) f in
  main paired
and zygo_both helper main (Fix f) =
  let paired = map_f (fun child -> zygo_both helper main child) f in
  let b_layer = map_f snd paired in
  let ab_layer = paired in
  (main ab_layer, helper b_layer)

(* Approach 1: "Is this expression safe?" depends on evaluation *)
(* Helper: evaluate. Main: check if safe (no division by zero, etc.) *)
let eval_helper = function
  | LitF n -> n
  | AddF (a, b) -> a + b
  | MulF (a, b) -> a * b
  | NegF a -> -a

(* "Safe" means no multiplication by a value that could overflow *)
let safe_main = function
  | LitF _ -> true
  | AddF ((a, _), (b, _)) -> a && b
  | MulF ((a, va), (b, vb)) -> a && b && abs va < 1000 && abs vb < 1000
  | NegF (a, _) -> a

(* Approach 2: Pretty print with precedence *)
(* Helper: compute precedence. Main: add parens only when needed. *)
let prec_helper = function
  | LitF _ -> 100
  | AddF _ -> 1
  | MulF _ -> 2
  | NegF _ -> 3

let show_main = function
  | LitF n -> string_of_int n
  | AddF ((a, pa), (b, pb)) ->
    let la = if pa < 1 then "(" ^ a ^ ")" else a in
    let rb = if pb < 1 then "(" ^ b ^ ")" else b in
    la ^ " + " ^ rb
  | MulF ((a, pa), (b, pb)) ->
    let la = if pa < 2 then "(" ^ a ^ ")" else a in
    let rb = if pb < 2 then "(" ^ b ^ ")" else b in
    la ^ " * " ^ rb
  | NegF (a, _) -> "-" ^ a

(* Approach 3: Count and sum simultaneously *)
let count_helper = function
  | LitF _ -> 1
  | AddF (a, b) | MulF (a, b) -> a + b
  | NegF a -> a

let avg_main = function
  | LitF n -> float_of_int n
  | AddF ((a, ca), (b, cb)) -> (a *. float_of_int ca +. b *. float_of_int cb) /. float_of_int (ca + cb)
  | MulF ((_, _), (_, _)) -> 0.0 (* simplified *)
  | NegF (a, _) -> -. a

(* Builders *)
let lit n = Fix (LitF n)
let add a b = Fix (AddF (a, b))
let mul a b = Fix (MulF (a, b))
let neg a = Fix (NegF a)

(* === Tests === *)
let () =
  let e = add (lit 3) (mul (lit 4) (lit 5)) in

  (* Safety check *)
  let safe = zygo_eff eval_helper safe_main e in
  assert safe;

  let unsafe_e = mul (lit 99999) (lit 99999) in
  let not_safe = zygo_eff eval_helper safe_main unsafe_e in
  assert (not not_safe);

  (* Show with precedence *)
  let e2 = mul (add (lit 1) (lit 2)) (lit 3) in
  let shown = zygo_eff prec_helper show_main e2 in
  assert (shown = "(1 + 2) * 3");

  let e3 = add (lit 1) (mul (lit 2) (lit 3)) in
  let shown3 = zygo_eff prec_helper show_main e3 in
  assert (shown3 = "1 + 2 * 3");

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 223 — Zygomorphism

zygo Definition

OCaml

🐪 Show OCaml equivalent

let rec zygo_both helper main (Fix f) =
let paired = map_f (fun child -> zygo_both helper main child) f in
let b_layer = map_f snd paired in
(main paired, helper b_layer)

Rust

fn zygo_both<A: Clone, B: Clone>(
 helper: &dyn Fn(ExprF<B>) -> B,
 main: &dyn Fn(ExprF<(A, B)>) -> A,
 fix: &Fix,
) -> (A, B) {
 let paired = fix.0.map_ref(|child| zygo_both(helper, main, child));
 let b_layer = paired.map_ref(|(_, b)| b.clone());
 (main(paired.clone()), helper(b_layer))
}

Pretty Print with Precedence

OCaml

🐪 Show OCaml equivalent

let prec_helper = function LitF _ -> 100 | AddF _ -> 1 | MulF _ -> 2 | NegF _ -> 3

let show_main = function
| MulF ((a, pa), (b, pb)) ->
 let la = if pa < 2 then "(" ^ a ^ ")" else a in
 la ^ " * " ^ (if pb < 2 then "(" ^ b ^ ")" else b)

Rust

fn prec_helper(e: ExprF<u32>) -> u32 {
 match e { ExprF::LitF(_) => 100, ExprF::AddF(..) => 1, ExprF::MulF(..) => 2, ExprF::NegF(_) => 3 }
}

fn show_main(e: ExprF<(String, u32)>) -> String {
 match e {
     ExprF::MulF((a, pa), (b, pb)) => {
         let la = if pa < 2 { format!("({a})") } else { a };
         format!("{la} * {}", if pb < 2 { format!("({b})") } else { b })
     }
     ...
 }
}

223: Zygomorphism

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 223 — Zygomorphism

zygo Definition

OCaml

Rust

Pretty Print with Precedence

OCaml

Rust

Related Examples