224 Expert

Mutumorphism — Genuinely Mutual Recursion

Functional Programming

Tutorial

The Problem

Mutually recursive functions — is_even and is_odd depending on each other — are natural in mathematics but require mutual let rec in functional languages. A mutumorphism generalizes this: two folds that are mutually dependent, each using the other's result at each recursive step. Unlike zygomorphism (one feeds the other), mutumorphism has symmetric dependency. The classic example: is_even(n) uses is_odd(n-1) and vice versa.

🎯 Learning Outcomes

• Understand mutumorphisms as mutually recursive catamorphisms

• Learn how mutu computes two results simultaneously in one traversal

• See is_even/is_odd as the canonical mutumorphism example

• Understand the difference between zygo (one-way dependency) and mutu (two-way dependency)

Code Example

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

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)

Key Differences

Native mutual recursion: OCaml's let rec ... and expresses mutual recursion directly; Rust's fn definitions can call each other directly too — mutu is the structured/compositional version.

First-class capture: mutu captures the mutual recursion as a composable value; native let rec ... and is not first-class.

Zygomorphism vs. mutumorphism: zygo has one-way dependency (A uses B's results); mutu has two-way dependency (A uses B's and B uses A's).

Practical use: Mutual recursion arises in grammar parsers (expression/statement), type checkers (term/type), and game AI (agent/environment).

OCaml Approach

OCaml's let rec ... and provides native mutual recursion:

let rec is_even n = if n = 0 then true else is_odd (n - 1)
and is_odd n = if n = 0 then false else is_even (n - 1)

OCaml's native mutual recursion is more readable than the mutu scheme for simple cases. The mutu formulation is useful when the mutual structure must be captured as a first-class value (e.g., for testing or transformation).

Full Source

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

✓ Tests Rust test suite

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

Deep Comparison

Comparison: Example 224 — Mutumorphism

mutu Definition

OCaml

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

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

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

Exercises

Implement count_even_odd(n) using mutu: count how many even and odd numbers exist in [0..n] in one traversal.

Write a mutu-based tree algorithm: min_leaf and max_leaf computed simultaneously.

Express the Fibonacci sequence using mutu: fib(n) and fib(n+1) computed together.

Open Source Repos

functional-rust

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

Rust