074 — Catamorphism

Difficulty: ⭐⭐⭐ Advanced Category: Monadic patterns Concept: Generalized fold that replaces constructors with functions Key Insight: OCaml's labeled arguments (`~leaf`, `~node`) make catamorphism definitions beautifully readable. Rust requires `&dyn Fn` trait objects or generics, making the pattern more explicit but more verbose.

Run

cargo test

/// # Catamorphism — Generalized Fold on ADTs
///
/// A catamorphism replaces each constructor of an algebraic data type
/// with a function. It's the universal way to consume a recursive structure.

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

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

/// The catamorphism: replace Leaf with `leaf` value, Node with `node` function.
/// This is the most general way to fold over a tree.
pub fn cata<T, R>(
    tree: &Tree<T>,
    leaf: R,
    node: &dyn Fn(R, &T, R) -> R,
) -> R
where
    R: Clone,
{
    match tree {
        Tree::Leaf => leaf,
        Tree::Node(l, v, r) => {
            let left_result = cata(l, leaf.clone(), node);
            let right_result = cata(r, leaf, node);
            node(left_result, v, right_result)
        }
    }
}

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

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

/// Height: longest path from root to leaf
pub fn height<T>(tree: &Tree<T>) -> usize {
    cata(tree, 0, &|l, _, r| 1 + l.max(r))
}

/// Mirror: swap left and right subtrees
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_list<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    cata(tree, vec![], &|mut l, v, r| {
        l.push(v.clone());
        l.extend(r);
        l
    })
}

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

    fn sample_tree() -> 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_tree()), 3);
        assert_eq!(size::<i64>(&Tree::Leaf), 0);
    }

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

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

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

    #[test]
    fn test_to_list() {
        assert_eq!(to_list(&sample_tree()), vec![1, 2, 3]);
    }

    #[test]
    fn test_catamorphism_is_general() {
        // Any tree computation can be expressed as a cata
        let product = cata(&sample_tree(), 1i64, &|l, v, r| l * v * r);
        assert_eq!(product, 6); // 1 * 1 * 2 * 1 * 3 * 1 = 6... wait
        // Actually: Node(Node(Leaf,1,Leaf), 2, Node(Leaf,3,Leaf))
        // = node(node(1, 1, 1), 2, node(1, 3, 1)) = node(1, 2, 3) = 1*2*3 = 6
        assert_eq!(product, 6);
    }
}

fn main() {
    println!("{:?}", size(&sample_tree()), 3);
    println!("{:?}", size::<i64>(&Tree::Leaf), 0);
    println!("{:?}", sum(&sample_tree()), 6);
}

(* Catamorphism — Generalized Fold on ADTs *)
(* Replace constructors with functions *)

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

(* The catamorphism: replace Leaf with ~leaf, Node with ~node *)
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
  Printf.printf "size=%d sum=%d height=%d\n" (size t) (sum t) (height t);
  List.iter (Printf.printf "%d ") (to_list (mirror t));
  print_newline ();
  assert (size t = 3);
  assert (sum t = 6);
  assert (height t = 2);
  Printf.printf "All catamorphism tests passed!\n"

📊 Detailed Comparison

Catamorphism — OCaml vs Rust Comparison

Core Insight

A catamorphism is the "universal fold" over any algebraic data type. You replace each constructor with a function: `Leaf → leaf_value`, `Node(l,v,r) → node_fn(l_result, v, r_result)`. Once you have `cata`, any tree computation (size, sum, height, mirror) is just choosing the right leaf and node functions.

OCaml Approach

Labeled arguments make the pattern crystal clear: `cata ~leaf:0 ~node:(fun l _ r -> 1 + l + r)` reads almost like a specification. The parametric polymorphism of the return type means `cata` can produce any type — integers, trees, lists. OCaml's GC handles all the intermediate allocations.

Rust Approach

Uses `&dyn Fn(R, &T, R) -> R` for the node function — dynamic dispatch via trait objects. The `R: Clone` bound is needed because the leaf value must be cloned for each leaf in the tree. `mirror` can't easily use `cata` because it needs to produce `Tree<T>` which involves ownership — showing where Rust's ownership model creates friction with generic recursive patterns.

Comparison Table

Aspect	OCaml	Rust
Memory	GC handles all allocations	Clone bound for leaf, Box for nodes
Null safety	N/A	N/A
Errors	N/A	Ownership issues with tree-producing cata
Iteration	Recursive pattern match	Recursive pattern match
Ergonomics	Labeled args (`~leaf ~node`)	Trait objects (`&dyn Fn`)

Things Rust Learners Should Notice

1. `&dyn Fn` vs generic `F: Fn` — dyn dispatch avoids monomorphization bloat for recursive calls 2. `R: Clone` — the leaf value must be cloneable since it's used at every leaf position 3. `Box<Tree<T>>` — recursive types need indirection in Rust (Box) but not in OCaml 4. Mirror breaks the pattern — producing a `Tree` from `cata` requires Clone on `T` and fighting ownership 5. Category theory connection — catamorphisms are the theoretical foundation of `fold` / `reduce`