867 Fundamental

867-foldable-tree — Foldable Tree

Functional Programming

Tutorial

The Problem

A fold over a list collapses it into a single value by processing each element sequentially. Extending this idea to trees requires choosing a traversal order — in-order, pre-order, or post-order — each of which imposes a different visitation sequence on nodes. The Foldable abstraction from Haskell and OCaml formalizes this: any container that supports a fold is "foldable," meaning every aggregate operation (sum, count, to-list, membership) can be derived from a single generic fold. This example implements three tree folds in Rust and derives higher-order operations from them.

🎯 Learning Outcomes

• Understand in-order, pre-order, and post-order traversal as distinct fold variants

• Derive higher-order operations (sum, collect, count) from a single fold abstraction

• Use recursive pattern matching on Rust enums to walk recursive data structures

• Compare Rust's explicit mutable closure passing with OCaml's polymorphic fold style

• Recognize the Foldable pattern as a key abstraction in functional programming

Code Example

fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
    match self {
        Tree::Leaf => init,
        Tree::Node(l, v, r) => {
            let acc = l.fold_inorder(init, f);
            let acc = f(acc, v);
            r.fold_inorder(acc, f)
        }
    }
}

let rec fold_inorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_inorder f acc l in
    let acc = f acc v in
    fold_inorder f acc r

Key Differences

Closure mutability: Rust requires &mut impl FnMut for stateful accumulators; OCaml closures can capture mutable state through ref cells or functional accumulation.

Recursive type boxing: Rust needs Box<Tree<T>> to break the infinite-size cycle; OCaml's GC-managed heap handles this transparently.

Monomorphization: Rust generates specialized code per closure type; OCaml uses uniform value representation.

Derived operations: Both languages derive all operations from a single fold, but OCaml expresses this more concisely via the pipe operator and partial application.

OCaml Approach

OCaml fold functions use curried style: fold_inorder f acc tree. Pattern matching on Leaf | Node(l, v, r) threads the accumulator left-to-right. Derived operations like to_list_inorder are one-liners combining fold with cons-prepend and List.rev. OCaml's implicit currying makes partial application natural, and let rec co-defines mutually recursive functions. The Rust version achieves the same generality using explicit trait bounds and monomorphized closures.

Full Source

#![allow(clippy::all)]
// Example 068: Foldable for Binary Tree
// Left/right fold, collect all values, various aggregations

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

impl<T> Tree<T> {
    fn node(l: Tree<T>, v: T, r: Tree<T>) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }

    // Approach 1: In-order fold
    fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = l.fold_inorder(init, f);
                let acc = f(acc, v);
                r.fold_inorder(acc, f)
            }
        }
    }

    // Approach 2: Pre-order and post-order
    fn fold_preorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = f(init, v);
                let acc = l.fold_preorder(acc, f);
                r.fold_preorder(acc, f)
            }
        }
    }

    fn fold_postorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
        match self {
            Tree::Leaf => init,
            Tree::Node(l, v, r) => {
                let acc = l.fold_postorder(init, f);
                let acc = r.fold_postorder(acc, f);
                f(acc, v)
            }
        }
    }
}

// Approach 3: Derived operations
impl Tree<i32> {
    fn to_vec_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.fold_inorder((), &mut |(), x| {
            result.push(*x);
        });
        result
    }

    fn sum(&self) -> i32 {
        self.fold_inorder(0, &mut |acc, x| acc + x)
    }

    fn max_val(&self) -> Option<i32> {
        self.fold_inorder(None, &mut |acc: Option<i32>, x| {
            Some(acc.map_or(*x, |a| a.max(*x)))
        })
    }

    fn all(&self, pred: impl Fn(&i32) -> bool) -> bool {
        self.fold_inorder(true, &mut |acc, x| acc && pred(x))
    }

    fn any(&self, pred: impl Fn(&i32) -> bool) -> bool {
        self.fold_inorder(false, &mut |acc, x| acc || pred(x))
    }

    fn count(&self, pred: impl Fn(&i32) -> bool) -> usize {
        self.fold_inorder(0, &mut |acc, x| if pred(x) { acc + 1 } else { acc })
    }
}

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

    fn sample_tree() -> Tree<i32> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(
                Tree::node(Tree::Leaf, 3, Tree::Leaf),
                4,
                Tree::node(Tree::Leaf, 5, Tree::Leaf),
            ),
        )
    }

    #[test]
    fn test_inorder() {
        assert_eq!(sample_tree().to_vec_inorder(), vec![1, 2, 3, 4, 5]);
    }

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

    #[test]
    fn test_max() {
        assert_eq!(sample_tree().max_val(), Some(5));
    }

    #[test]
    fn test_all() {
        assert!(sample_tree().all(|x| *x > 0));
        assert!(!sample_tree().all(|x| *x > 2));
    }

    #[test]
    fn test_any() {
        assert!(sample_tree().any(|x| *x == 3));
        assert!(!sample_tree().any(|x| *x == 99));
    }

    #[test]
    fn test_count() {
        assert_eq!(sample_tree().count(|x| x % 2 == 0), 2);
    }

    #[test]
    fn test_preorder() {
        let mut result = Vec::new();
        sample_tree().fold_preorder((), &mut |(), x| {
            result.push(*x);
        });
        assert_eq!(result, vec![2, 1, 4, 3, 5]);
    }

    #[test]
    fn test_postorder() {
        let mut result = Vec::new();
        sample_tree().fold_postorder((), &mut |(), x| {
            result.push(*x);
        });
        assert_eq!(result, vec![1, 3, 5, 4, 2]);
    }

    #[test]
    fn test_empty_tree() {
        let t = Tree::<i32>::Leaf;
        assert_eq!(t.sum(), 0);
        assert_eq!(t.max_val(), None);
    }
}

(* Example 068: Foldable for Binary Tree *)
(* Left/right fold, collect all values, various aggregations *)

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

(* Approach 1: In-order fold (left, value, right) *)
let rec fold_inorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_inorder f acc l in
    let acc = f acc v in
    fold_inorder f acc r

(* Approach 2: Pre-order and post-order *)
let rec fold_preorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = f acc v in
    let acc = fold_preorder f acc l in
    fold_preorder f acc r

let rec fold_postorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_postorder f acc l in
    let acc = fold_postorder f acc r in
    f acc v

(* Approach 3: Derived operations *)
let to_list_inorder tree = List.rev (fold_inorder (fun acc x -> x :: acc) [] tree)
let sum tree = fold_inorder (+) 0 tree
let max_val tree = fold_inorder (fun acc x -> max acc x) min_int tree
let all pred tree = fold_inorder (fun acc x -> acc && pred x) true tree
let any pred tree = fold_inorder (fun acc x -> acc || pred x) false tree
let count pred tree = fold_inorder (fun acc x -> if pred x then acc + 1 else acc) 0 tree

let () =
  let tree = Node (Node (Leaf, 1, Leaf), 2, Node (Node (Leaf, 3, Leaf), 4, Node (Leaf, 5, Leaf))) in

  assert (to_list_inorder tree = [1; 2; 3; 4; 5]);
  assert (sum tree = 15);
  assert (max_val tree = 5);
  assert (all (fun x -> x > 0) tree = true);
  assert (all (fun x -> x > 2) tree = false);
  assert (any (fun x -> x = 3) tree = true);
  assert (count (fun x -> x mod 2 = 0) tree = 2);

  (* Pre-order: root first *)
  let pre = List.rev (fold_preorder (fun acc x -> x :: acc) [] tree) in
  assert (pre = [2; 1; 4; 3; 5]);

  (* Post-order: root last *)
  let post = List.rev (fold_postorder (fun acc x -> x :: acc) [] tree) in
  assert (post = [1; 3; 5; 4; 2]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    fn sample_tree() -> Tree<i32> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(
                Tree::node(Tree::Leaf, 3, Tree::Leaf),
                4,
                Tree::node(Tree::Leaf, 5, Tree::Leaf),
            ),
        )
    }

    #[test]
    fn test_inorder() {
        assert_eq!(sample_tree().to_vec_inorder(), vec![1, 2, 3, 4, 5]);
    }

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

    #[test]
    fn test_max() {
        assert_eq!(sample_tree().max_val(), Some(5));
    }

    #[test]
    fn test_all() {
        assert!(sample_tree().all(|x| *x > 0));
        assert!(!sample_tree().all(|x| *x > 2));
    }

    #[test]
    fn test_any() {
        assert!(sample_tree().any(|x| *x == 3));
        assert!(!sample_tree().any(|x| *x == 99));
    }

    #[test]
    fn test_count() {
        assert_eq!(sample_tree().count(|x| x % 2 == 0), 2);
    }

    #[test]
    fn test_preorder() {
        let mut result = Vec::new();
        sample_tree().fold_preorder((), &mut |(), x| {
            result.push(*x);
        });
        assert_eq!(result, vec![2, 1, 4, 3, 5]);
    }

    #[test]
    fn test_postorder() {
        let mut result = Vec::new();
        sample_tree().fold_postorder((), &mut |(), x| {
            result.push(*x);
        });
        assert_eq!(result, vec![1, 3, 5, 4, 2]);
    }

    #[test]
    fn test_empty_tree() {
        let t = Tree::<i32>::Leaf;
        assert_eq!(t.sum(), 0);
        assert_eq!(t.max_val(), None);
    }
}

Deep Comparison

Comparison: Foldable for Binary Tree

In-Order Fold

OCaml:

let rec fold_inorder f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_inorder f acc l in
    let acc = f acc v in
    fold_inorder f acc r

Rust:

fn fold_inorder<B>(&self, init: B, f: &mut impl FnMut(B, &T) -> B) -> B {
    match self {
        Tree::Leaf => init,
        Tree::Node(l, v, r) => {
            let acc = l.fold_inorder(init, f);
            let acc = f(acc, v);
            r.fold_inorder(acc, f)
        }
    }
}

Derived Operations

OCaml:

let sum tree = fold_inorder (+) 0 tree
let all pred tree = fold_inorder (fun acc x -> acc && pred x) true tree

Rust:

fn sum(&self) -> i32 { self.fold_inorder(0, &mut |acc, x| acc + x) }
fn all(&self, pred: impl Fn(&i32) -> bool) -> bool {
    self.fold_inorder(true, &mut |acc, x| acc && pred(x))
}

Exercises

Add fold_levelorder that visits nodes breadth-first using a VecDeque as the traversal queue.

Implement zip_trees that pairs corresponding nodes from two same-shaped trees, returning None on shape mismatch.

Implement find_first on top of fold_inorder using Option as the accumulator to short-circuit at the first matching element.

Open Source Repos

functional-rust

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

Rust