080 Expert

080 — Catamorphism

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "080 — Catamorphism" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Implement a generalized fold (catamorphism) over a binary tree ADT. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Implement a generalized fold (catamorphism) over a binary tree ADT. The cata function replaces each constructor with a provided function, enabling size, sum, height, mirror, and to_vec to be expressed as single cata calls — demonstrating the principle of replacing recursive case analysis with higher-order structure.

🎯 Learning Outcomes

• Understand catamorphisms as the canonical way to eliminate a recursive data type

• Pass &dyn Fn closures to avoid monomorphizing cata for every use case

• Recognise that mirror cannot use the generic cata signature because it returns Tree<T> (same type)

• See how leaf_val.clone() is needed when the accumulator is split across two branches

• Map Rust's cata to OCaml's labeled-argument ~leaf ~node style

• Identify when a direct recursive function is clearer than a catamorphism

Code Example

#![allow(clippy::all)]
/// Catamorphism — Generalized Fold on ADTs
///
/// Ownership insight: The catamorphism takes closures by reference (&dyn Fn).
/// The tree is borrowed for folding, owned for mirror (which builds new tree).

#[derive(Debug, PartialEq, Clone)]
pub enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn node(left: Tree<T>, val: T, right: Tree<T>) -> Self {
        Tree::Node(Box::new(left), val, Box::new(right))
    }
}

/// Catamorphism: replaces constructors with functions
/// leaf_fn replaces Leaf, node_fn replaces Node
pub fn cata<T, R>(tree: &Tree<T>, leaf_val: R, node_fn: &dyn Fn(R, &T, R) -> R) -> R
where
    R: Clone,
{
    match tree {
        Tree::Leaf => leaf_val,
        Tree::Node(l, v, r) => {
            let left = cata(l, leaf_val.clone(), node_fn);
            let right = cata(r, leaf_val.clone(), node_fn);
            node_fn(left, v, right)
        }
    }
}

pub fn size<T>(tree: &Tree<T>) -> usize {
    cata(tree, 0, &|l, _, r| 1 + l + r)
}

pub fn sum(tree: &Tree<i64>) -> i64 {
    cata(tree, 0, &|l, v, r| l + v + r)
}

pub fn height<T>(tree: &Tree<T>) -> usize {
    cata(tree, 0, &|l, _, r| 1 + l.max(r))
}

/// Mirror requires building a new tree — different signature
pub fn mirror<T: Clone>(tree: &Tree<T>) -> Tree<T> {
    match tree {
        Tree::Leaf => Tree::Leaf,
        Tree::Node(l, v, r) => Tree::node(mirror(r), v.clone(), mirror(l)),
    }
}

/// In-order traversal to list
pub fn to_vec<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(l, v, r) => {
            let mut result = to_vec(l);
            result.push(v.clone());
            result.extend(to_vec(r));
            result
        }
    }
}

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

    fn sample() -> Tree<i64> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 3);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&sample()), 6);
    }

    #[test]
    fn test_height() {
        assert_eq!(height(&sample()), 2);
    }

    #[test]
    fn test_mirror() {
        let m = mirror(&sample());
        assert_eq!(to_vec(&m), vec![3, 2, 1]);
    }

    #[test]
    fn test_to_vec() {
        assert_eq!(to_vec(&sample()), vec![1, 2, 3]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(size::<i64>(&Tree::Leaf), 0);
        assert_eq!(height::<i64>(&Tree::Leaf), 0);
    }
}

(* Catamorphism — Generalized Fold on ADTs *)

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

(* The catamorphism replaces constructors with functions *)
let rec cata ~leaf ~node = function
  | Leaf -> leaf
  | Node (l, v, r) -> node (cata ~leaf ~node l) v (cata ~leaf ~node r)

let size = cata ~leaf:0 ~node:(fun l _ r -> 1 + l + r)
let sum = cata ~leaf:0 ~node:(fun l v r -> l + v + r)
let height = cata ~leaf:0 ~node:(fun l _ r -> 1 + max l r)
let mirror = cata ~leaf:Leaf ~node:(fun l v r -> Node (r, v, l))
let to_list = cata ~leaf:[] ~node:(fun l v r -> l @ [v] @ r)

let () =
  let t = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) in
  assert (size t = 3);
  assert (sum t = 6);
  assert (height t = 2);
  assert (to_list (mirror t) = [3; 2; 1])

Key Differences

Aspect	Rust	OCaml
Signature	`leaf_val: R, node_fn: &dyn Fn(R, &T, R) -> R`	`~leaf ~node` labeled args
Constraint	`R: Clone` for branch splitting	Not needed (structural sharing)
Mirror	Separate direct recursion	Expressible as catamorphism
Tree node	`Box<Tree<T>>`	`'a tree` (native recursive)
Dispatch	`&dyn Fn` (dynamic)	Native closure (monomorphized)
Clarity	Verbose but explicit	Concise, labeled

Catamorphisms unify all structural recursions over a type into a single combinator. When an operation can be expressed as a catamorphism, it gains free structural safety: the recursion is handled once, correctly, and the user only provides the algebra.

OCaml Approach

OCaml uses labeled arguments ~leaf and ~node for the catamorphism, making call sites self-documenting: cata ~leaf:0 ~node:(fun l _ r -> 1 + l + r). Because OCaml uses structural sharing for lists and native recursive types, there is no need for Clone. mirror fits naturally as a catamorphism: ~node:(fun l v r -> Node(r, v, l)) simply swaps the already-folded children. The conciseness difference is mainly the absence of Box and Clone.

Full Source

#![allow(clippy::all)]
/// Catamorphism — Generalized Fold on ADTs
///
/// Ownership insight: The catamorphism takes closures by reference (&dyn Fn).
/// The tree is borrowed for folding, owned for mirror (which builds new tree).

#[derive(Debug, PartialEq, Clone)]
pub enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn node(left: Tree<T>, val: T, right: Tree<T>) -> Self {
        Tree::Node(Box::new(left), val, Box::new(right))
    }
}

/// Catamorphism: replaces constructors with functions
/// leaf_fn replaces Leaf, node_fn replaces Node
pub fn cata<T, R>(tree: &Tree<T>, leaf_val: R, node_fn: &dyn Fn(R, &T, R) -> R) -> R
where
    R: Clone,
{
    match tree {
        Tree::Leaf => leaf_val,
        Tree::Node(l, v, r) => {
            let left = cata(l, leaf_val.clone(), node_fn);
            let right = cata(r, leaf_val.clone(), node_fn);
            node_fn(left, v, right)
        }
    }
}

pub fn size<T>(tree: &Tree<T>) -> usize {
    cata(tree, 0, &|l, _, r| 1 + l + r)
}

pub fn sum(tree: &Tree<i64>) -> i64 {
    cata(tree, 0, &|l, v, r| l + v + r)
}

pub fn height<T>(tree: &Tree<T>) -> usize {
    cata(tree, 0, &|l, _, r| 1 + l.max(r))
}

/// Mirror requires building a new tree — different signature
pub fn mirror<T: Clone>(tree: &Tree<T>) -> Tree<T> {
    match tree {
        Tree::Leaf => Tree::Leaf,
        Tree::Node(l, v, r) => Tree::node(mirror(r), v.clone(), mirror(l)),
    }
}

/// In-order traversal to list
pub fn to_vec<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf => vec![],
        Tree::Node(l, v, r) => {
            let mut result = to_vec(l);
            result.push(v.clone());
            result.extend(to_vec(r));
            result
        }
    }
}

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

    fn sample() -> Tree<i64> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 3);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&sample()), 6);
    }

    #[test]
    fn test_height() {
        assert_eq!(height(&sample()), 2);
    }

    #[test]
    fn test_mirror() {
        let m = mirror(&sample());
        assert_eq!(to_vec(&m), vec![3, 2, 1]);
    }

    #[test]
    fn test_to_vec() {
        assert_eq!(to_vec(&sample()), vec![1, 2, 3]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(size::<i64>(&Tree::Leaf), 0);
        assert_eq!(height::<i64>(&Tree::Leaf), 0);
    }
}

(* Catamorphism — Generalized Fold on ADTs *)

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

(* The catamorphism replaces constructors with functions *)
let rec cata ~leaf ~node = function
  | Leaf -> leaf
  | Node (l, v, r) -> node (cata ~leaf ~node l) v (cata ~leaf ~node r)

let size = cata ~leaf:0 ~node:(fun l _ r -> 1 + l + r)
let sum = cata ~leaf:0 ~node:(fun l v r -> l + v + r)
let height = cata ~leaf:0 ~node:(fun l _ r -> 1 + max l r)
let mirror = cata ~leaf:Leaf ~node:(fun l v r -> Node (r, v, l))
let to_list = cata ~leaf:[] ~node:(fun l v r -> l @ [v] @ r)

let () =
  let t = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) in
  assert (size t = 3);
  assert (sum t = 6);
  assert (height t = 2);
  assert (to_list (mirror t) = [3; 2; 1])

✓ Tests Rust test suite

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

    fn sample() -> Tree<i64> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_size() {
        assert_eq!(size(&sample()), 3);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&sample()), 6);
    }

    #[test]
    fn test_height() {
        assert_eq!(height(&sample()), 2);
    }

    #[test]
    fn test_mirror() {
        let m = mirror(&sample());
        assert_eq!(to_vec(&m), vec![3, 2, 1]);
    }

    #[test]
    fn test_to_vec() {
        assert_eq!(to_vec(&sample()), vec![1, 2, 3]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(size::<i64>(&Tree::Leaf), 0);
        assert_eq!(height::<i64>(&Tree::Leaf), 0);
    }
}

Deep Comparison

Catamorphism — Comparison

Core Insight

A catamorphism generalizes fold to any algebraic data type by replacing each constructor with a function. OCaml's labeled arguments and polymorphic recursion make this pattern concise. Rust needs explicit Clone bounds and &dyn Fn for the closure parameters.

OCaml Approach

• let rec cata ~leaf ~node = function ... — labeled args for clarity

• let size = cata ~leaf:0 ~node:(fun l _ r -> 1 + l + r) — partial application

• mirror returns a tree — same catamorphism, different result type

• Polymorphic: works for any 'a tree

Rust Approach

• pub fn cata<T, R>(tree: &Tree<T>, leaf_val: R, node_fn: &dyn Fn(R, &T, R) -> R)

• R: Clone bound needed because leaf_val is used in multiple branches

• mirror can't use the same cata signature (returns Tree, not a fold)

• Separate implementation for operations that build trees

Comparison Table

Aspect	OCaml	Rust
Constructor replacement	Labeled args	Closure parameters
Partial application	`let size = cata ~leaf:0 ~node:...`	Standalone function
Clone requirement	None (GC)	`R: Clone`
Mirror via cata	Yes (returns tree)	No (different signature)
Polymorphism	`'a tree`	`Tree<T>` with bounds

Learner Notes

• Catamorphisms are the "design pattern" of functional programming

• In Rust, &dyn Fn is needed for recursive closures (can't use generics easily)

• OCaml's labeled arguments (~leaf, ~node) have no direct Rust equivalent

• Consider trait-based visitors as an alternative Rust pattern

Exercises

Add a depth_at function using cata that returns the depth (level) of the first node with a given value.

Implement flatten_bfs: Tree<T> -> Vec<T> using a queue rather than cata. Compare its readability with the catamorphism approach.

Extend cata to work on a ternary tree TTree<T> = Leaf | Node(Box<TTree<T>>, T, Box<TTree<T>>, Box<TTree<T>>).

Write an anamorphism (unfold) dual: given a seed and a step function S -> Option<(S, T, S)>, build a Tree<T>.

In OCaml, use the catamorphism to implement a map function cata ~leaf:Leaf ~node:(fun l v r -> Node(l, f v, r)). Verify it satisfies the functor laws.

Open Source Repos

functional-rust

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

Rust