069: Traversable Tree

Difficulty: 3 Level: Advanced Map a function with effects (Option/Result) over every tree node — fail fast if any node fails.

The Problem This Solves

You have a binary tree of strings and you want to parse every node as an integer. If all parses succeed, you want a tree of integers. If any node fails, you want the whole operation to fail with an error — not a tree with `None` leaves mixed in. This is the traverse operation: like `map`, but the function returns an effect (`Option<U>`, `Result<U, E>`) and the tree is only returned if all effects succeed. It's the difference between "transform and keep going" (map) and "transform but stop on first failure" (traverse). In Python you'd wrap everything in a try/except and catch the first ValueError. In Rust, the `?` operator does this structurally — each recursive call uses `?` for early exit, and the code reads almost like pure code without the error handling noise.

The Intuition

Pure `map`: apply `f` to each node value. `f` always succeeds. Returns a new tree. `traverse` with `Option`: apply `f` to each node value. `f` might return `None`. If any node returns `None`, the whole traversal returns `None`. Otherwise returns `Some(new_tree)`. This is "all or nothing." `traverse` with `Result`: same idea but with error values. The first `Err` short-circuits the traversal and is returned directly. `Ok(new_tree)` only if every node succeeds. The key insight: Traversable separates structure (the tree shape) from effects (Option, Result, IO, etc.). You write one `traverse` per effect type, and the tree structure handling stays constant. In OCaml, implementing `traverse` for a deeply nested tree requires explicit pattern matching at each level — matching the left subtree result, the node result, and the right subtree result produces deeply nested code. Rust's `?` operator eliminates this nesting entirely — the code looks almost exactly like the pure `map` function.

How It Works in Rust

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

impl<T> Tree<T> {
 // Traverse with Option: None on any failure → None for whole tree
 fn traverse_option<U>(&self, f: &impl Fn(&T) -> Option<U>) -> Option<Tree<U>> {
     match self {
         Tree::Leaf => Some(Tree::Leaf),
         Tree::Node(l, v, r) => {
             let l2 = l.traverse_option(f)?;   // ? returns None immediately on failure
             let v2 = f(v)?;                    // ? short-circuits here if f returns None
             let r2 = r.traverse_option(f)?;
             Some(Tree::node(l2, v2, r2))       // only reached if all succeeded
         }
     }
 }

 // Traverse with Result: Err propagates immediately
 fn traverse_result<U, E>(&self, f: &impl Fn(&T) -> Result<U, E>) -> Result<Tree<U>, E> {
     match self {
         Tree::Leaf => Ok(Tree::Leaf),
         Tree::Node(l, v, r) => {
             let l2 = l.traverse_result(f)?;   // ? returns Err immediately on failure
             let v2 = f(v)?;
             let r2 = r.traverse_result(f)?;
             Ok(Tree::node(l2, v2, r2))
         }
     }
 }
}

Usage — parsing a tree of strings to integers:

let string_tree = Tree::node(
 Tree::Leaf, "42".to_string(), Tree::node(Tree::Leaf, "7".to_string(), Tree::Leaf)
);

// All succeed → Some(integer tree)
let int_tree = string_tree.traverse_option(|s| s.parse::<i32>().ok());

// One bad node → None for the whole thing
let bad_tree = Tree::node(
 Tree::Leaf, "42".to_string(), Tree::node(Tree::Leaf, "bad".to_string(), Tree::Leaf)
);
let result = bad_tree.traverse_option(|s| s.parse::<i32>().ok());
assert!(result.is_none());  // "bad" failed → whole thing is None

What This Unlocks

Validation trees: traverse with `Result<T, Vec<Error>>` to collect all errors, or `?` style to fail-fast — two different traversal strategies for the same tree.
IO over tree structures: traverse with `Result<T, io::Error>` to read files at every node, failing if any file is missing.
Configuration parsing: a tree of raw config values traversed with a validator returns a typed config tree or the first validation error.

Key Differences

Concept	OCaml	Rust
Pattern matching depth	Deeply nested `match`; each level matches the option/result	`?` operator linearizes: three `?` lines + return
Nesting count	`match (traverse_opt l) with Some l2 -> match (f v) ...`	`let l2 = ...?; let v2 = f(v)?; let r2 = ...?;`
Effect abstraction	Can write `traverse` generically over any monad via modules	Must implement separately per effect type (no HKT)
Tree ownership	OCaml reuses unchanged branches (GC sharing)	Rust builds a new owned tree — no sharing
Error collection	Same challenge — need Applicative not Monad for "collect all errors"	Same; use `Result<T, Vec<E>>` for accumulating

// Example 069: Traversable for Binary Tree
// Map over a tree with effects (Option/Result)

#[derive(Debug, PartialEq, Clone)]
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: Traverse with Option
    fn traverse_option<U>(&self, f: &impl Fn(&T) -> Option<U>) -> Option<Tree<U>> {
        match self {
            Tree::Leaf => Some(Tree::Leaf),
            Tree::Node(l, v, r) => {
                let l2 = l.traverse_option(f)?;
                let v2 = f(v)?;
                let r2 = r.traverse_option(f)?;
                Some(Tree::node(l2, v2, r2))
            }
        }
    }

    // Approach 2: Traverse with Result
    fn traverse_result<U, E>(&self, f: &impl Fn(&T) -> Result<U, E>) -> Result<Tree<U>, E> {
        match self {
            Tree::Leaf => Ok(Tree::Leaf),
            Tree::Node(l, v, r) => {
                let l2 = l.traverse_result(f)?;
                let v2 = f(v)?;
                let r2 = r.traverse_result(f)?;
                Ok(Tree::node(l2, v2, r2))
            }
        }
    }

    // Approach 3: Pure map (no effect)
    fn map<U>(&self, f: &impl Fn(&T) -> U) -> Tree<U> {
        match self {
            Tree::Leaf => Tree::Leaf,
            Tree::Node(l, v, r) => Tree::node(l.map(f), f(v), r.map(f)),
        }
    }

    fn to_vec(&self) -> Vec<&T> {
        match self {
            Tree::Leaf => vec![],
            Tree::Node(l, v, r) => {
                let mut result = l.to_vec();
                result.push(v);
                result.extend(r.to_vec());
                result
            }
        }
    }
}

fn safe_double(x: &i32) -> Option<i32> {
    if *x > 50 { None } else { Some(x * 2) }
}

fn parse_positive(x: &i32) -> Result<i32, String> {
    if *x > 0 { Ok(*x) } else { Err(format!("Not positive: {}", x)) }
}

fn main() {
    let tree = Tree::node(Tree::node(Tree::Leaf, 1, Tree::Leaf), 2, Tree::node(Tree::Leaf, 3, Tree::Leaf));
    println!("traverse_option: {:?}", tree.traverse_option(&safe_double));
    println!("traverse_result: {:?}", tree.traverse_result(&parse_positive));
    println!("map *2: {:?}", tree.map(&|x| x * 2));
}

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

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

    #[test]
    fn test_traverse_option_success() {
        let result = sample().traverse_option(&safe_double);
        let expected = Tree::node(Tree::node(Tree::Leaf, 2, Tree::Leaf), 4, Tree::node(Tree::Leaf, 6, Tree::Leaf));
        assert_eq!(result, Some(expected));
    }

    #[test]
    fn test_traverse_option_failure() {
        let tree = Tree::node(Tree::node(Tree::Leaf, 10, Tree::Leaf), 60, Tree::Leaf);
        assert_eq!(tree.traverse_option(&safe_double), None);
    }

    #[test]
    fn test_traverse_result_success() {
        assert_eq!(sample().traverse_result(&parse_positive), Ok(sample()));
    }

    #[test]
    fn test_traverse_result_failure() {
        let tree = Tree::node(Tree::Leaf, -1, Tree::Leaf);
        assert_eq!(tree.traverse_result(&parse_positive), Err("Not positive: -1".into()));
    }

    #[test]
    fn test_map() {
        let doubled = sample().map(&|x| x * 2);
        assert_eq!(doubled.to_vec(), vec![&2, &4, &6]);
    }

    #[test]
    fn test_traverse_leaf() {
        assert_eq!(Tree::<i32>::Leaf.traverse_option(&safe_double), Some(Tree::Leaf));
    }
}

(* Example 069: Traversable for Binary Tree *)
(* Map over a tree with effects (Option/Result) *)

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

(* Approach 1: Traverse with Option *)
let rec traverse_option f = function
  | Leaf -> Some Leaf
  | Node (l, v, r) ->
    match traverse_option f l with
    | None -> None
    | Some l' ->
      match f v with
      | None -> None
      | Some v' ->
        match traverse_option f r with
        | None -> None
        | Some r' -> Some (Node (l', v', r'))

(* Approach 2: Traverse with Result *)
let rec traverse_result f = function
  | Leaf -> Ok Leaf
  | Node (l, v, r) ->
    match traverse_result f l with
    | Error e -> Error e
    | Ok l' ->
      match f v with
      | Error e -> Error e
      | Ok v' ->
        match traverse_result f r with
        | Error e -> Error e
        | Ok r' -> Ok (Node (l', v', r'))

(* Approach 3: Map (traverse with identity effect) *)
let rec map f = function
  | Leaf -> Leaf
  | Node (l, v, r) -> Node (map f l, f v, map f r)

(* Test helpers *)
let safe_double x = if x > 50 then None else Some (x * 2)
let parse_positive x = if x > 0 then Ok x else Error (Printf.sprintf "Not positive: %d" x)

let rec to_list = function
  | Leaf -> []
  | Node (l, v, r) -> to_list l @ [v] @ to_list r

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

  (* Traverse Option — all succeed *)
  let result = traverse_option safe_double tree in
  assert (result = Some (Node (Node (Leaf, 2, Leaf), 4, Node (Leaf, 6, Leaf))));

  (* Traverse Option — one fails *)
  let big_tree = Node (Node (Leaf, 10, Leaf), 60, Leaf) in
  assert (traverse_option safe_double big_tree = None);

  (* Traverse Result *)
  assert (traverse_result parse_positive tree = Ok tree);
  let neg_tree = Node (Leaf, (-1), Leaf) in
  assert (traverse_result parse_positive neg_tree = Error "Not positive: -1");

  (* Map *)
  let doubled = map (fun x -> x * 2) tree in
  assert (to_list doubled = [2; 4; 6]);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Traversable for Binary Tree

Traverse with Option

OCaml:

🐪 Show OCaml equivalent

let rec traverse_option f = function
| Leaf -> Some Leaf
| Node (l, v, r) ->
 match traverse_option f l with
 | None -> None
 | Some l' -> match f v with
   | None -> None
   | Some v' -> match traverse_option f r with
     | None -> None
     | Some r' -> Some (Node (l', v', r'))

Rust (? operator makes it clean!):

fn traverse_option<U>(&self, f: &impl Fn(&T) -> Option<U>) -> Option<Tree<U>> {
 match self {
     Tree::Leaf => Some(Tree::Leaf),
     Tree::Node(l, v, r) => {
         let l2 = l.traverse_option(f)?;  // ? replaces nested match
         let v2 = f(v)?;
         let r2 = r.traverse_option(f)?;
         Some(Tree::node(l2, v2, r2))
     }
 }
}

Pure Map (No Effect)