• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed
• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection
• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops
• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably
• Chaining replaces nested loops with a readable, composable pipeline
#[derive(Debug, PartialEq, Clone)]
pub enum Tree<T> { Leaf, Node(Box<Tree<T>>, T, Box<Tree<T>>) }
/// The catamorphism for Tree<T>.
/// leaf_val: what Leaf maps to
/// node_fn: how to combine (left_result, node_value, right_result)
pub fn cata<T, R: Clone>(
tree: &Tree<T>,
leaf_val: R,
node_fn: &dyn Fn(R, &T, R) -> R,
) -> R {
match tree {
Tree::Leaf => leaf_val,
Tree::Node(l, v, r) => {
let left = cata(l, leaf_val.clone(), node_fn); // process left subtree
let right = cata(r, leaf_val.clone(), node_fn); // process right subtree
node_fn(left, v, right) // combine at this node
}
}
}
// All derived operations — no explicit recursion, just different functions
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))
}// Evaluator: pass arithmetic functions
let eval = |expr: &Expr| cata_expr(expr,
|n| n, // Lit(n) → n
|l, r| l + r, // Add → +
|l, r| l * r, // Mul → *
);
// Pretty-printer: pass string functions — same shape, different types
let pretty = |expr: &Expr| cata_expr(expr,
|n| n.to_string(),
|l, r| format!("({l} + {r})"),
|l, r| format!("({l} * {r})"),
);| Concept | OCaml | Rust |
|---|---|---|
| Catamorphism API | `cata ~leaf ~node tree` — labeled arguments, natural | `cata(tree, leaf_val, &dyn Fn(...))` — positional, explicit `&dyn` |
| Labeled arguments | `~leaf:(unit -> 'r)` makes call sites readable | No labels; order matters — document carefully |
| Clone bound | Not needed — GC handles sharing `leaf_val` | `R: Clone` required — `leaf_val` passed to both subtrees |
| Mirror (builds new tree) | Returns `tree` type — catamorphism works | Must break out of `cata` — return type is `Tree<T>`, not R=usize |
| Higher-rank types | Can abstract over functor shape | Fixed to `Tree<T>`; generalizing needs GATs |
/// 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);
}
}
fn main() {
println!("{:?}", size(&sample()), 3);
println!("{:?}", sum(&sample()), 6);
println!("{:?}", height(&sample()), 2);
}
(* 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])
| 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 |