868 Fundamental

868-traversable-tree — Traversable Tree

Functional Programming

Tutorial

The Problem

A Traversable structure extends Foldable by allowing each element to produce an effect, then collecting the results into the same shape. The canonical examples are: validate every node (returning Option<Tree<U>> — None if any node fails), or parse every node (returning Result<Tree<U>, E> — Err on first failure). This is formally the "traverse" operation from the Haskell Traversable typeclass. It is used in compilers for type-checking expression trees, in configuration validators that walk nested structures, and in reactive systems that need all-or-nothing transformation of data trees.

🎯 Learning Outcomes

• Understand the difference between map (no effects) and traverse (effectful map that can fail)

• Implement traverse_option and traverse_result for a binary tree

• Use the ? operator inside recursive tree functions to propagate failures

• Compare Rust's explicit Option/Result chaining with OCaml's monadic bind

• Recognize traverse as a unification of "map" and "sequence"

Code Example

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))
        }
    }
}

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'))

Key Differences

Error propagation: Rust uses ? inside recursive functions; OCaml uses explicit match or let* monadic bind.

No higher-kinded types: Rust cannot abstract over Option and Result in a single generic traverse; OCaml can via module functors parameterized on an applicative.

Tree shape preservation: Both preserve the tree structure on success and produce a flat error/none on failure.

Ownership: Rust traversal borrows &self and must clone subtrees into Some(Tree::node(...)) on success; OCaml reuses GC-managed nodes.

OCaml Approach

OCaml lacks the ? shorthand, so traversal is expressed as explicit pattern matches on None/Some and Error/Ok inside each recursive case. OCaml's Traversable typeclass equivalent requires a module functor parameterized over the applicative/monad. In practice, OCaml users write the specific traverse_option and traverse_result directly as shown in example.ml. With the let* syntax (OCaml 4.08+), monadic chains become readable without manual nesting.

Full Source

#![allow(clippy::all)]
// 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))
    }
}

#[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"

✓ Tests Rust test suite

#[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)
        );
    }
}

Deep Comparison

Comparison: Traversable for Binary Tree

Traverse with Option

OCaml:

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)

OCaml:

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

Rust:

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)),
    }
}

Exercises

Implement traverse_vec that applies f: &T -> Vec<U> to each node, returning a Vec<Tree<U>> with all combinations (cartesian product across nodes).

Add a sequence_option function that converts Tree<Option<T>> into Option<Tree<T>> using traverse_option with the identity function.

Implement validate_all that collects all Err values into a Vec<E> rather than stopping at the first, using a custom accumulating result type.

Open Source Repos

functional-rust

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

Rust