223 Expert

Zygomorphism — Two Mutually Dependent Folds

Functional Programming

Tutorial

The Problem

Sometimes two fold operations are interdependent: "compute the average" requires both the sum and the count simultaneously. Running two separate catamorphisms would traverse the structure twice. A zygomorphism runs two algebras in a single pass: a "helper" algebra computes auxiliary data, and the "main" algebra uses that auxiliary data alongside the recursive results. Named after the Greek for "yoke," it couples two folds together.

🎯 Learning Outcomes

• Understand zygomorphisms as paired catamorphisms sharing one traversal

• Learn how the helper algebra provides auxiliary data to the main algebra

• See "average" as a canonical example: sum and count computed together

• Understand the performance benefit: one traversal instead of two

Code Example

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

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)

Key Differences

Two passes vs. one: zygo combines two passes into one — equivalent to computing cata alg1 . cata alg2 but more efficient (one traversal, not two).

Dependency direction: The helper algebra's results feed into the main algebra, not vice versa — one-directional coupling.

Specialization: zygo specializes to cata when the main algebra ignores the helper (no dependency) and to para when the helper is the original structure (identity algebra).

Practical use: Statistics computation (mean + variance in one pass), tree balancing checks, and "labeled fold" patterns use zygomorphisms.

OCaml Approach

OCaml's zygomorphism:

let rec zygo helper main (Fix ef) =
  let pairs = map_expr_f (fun child -> (helper_result child, zygo helper main child)) ef in
  main pairs

The recursion threads both results together. OCaml's let rec handles the mutual recursion. In practice, OCaml code often uses para or plain let rec instead of named recursion schemes, but the zygo pattern is useful for demonstrating the concept.

Full Source

#![allow(clippy::all)]
// 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"

✓ Tests Rust test suite

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

Deep Comparison

Comparison: Example 223 — Zygomorphism

zygo Definition

OCaml

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

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 })
        }
        ...
    }
}

Exercises

Implement a zygo that computes both the sum and the product of a list in one traversal.

Write a tree zygomorphism that computes the average leaf value: helper computes (sum, count), main divides.

Implement "is balanced?" using a zygomorphism: helper computes height, main checks balance condition per node.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust