585 Fundamental

Pattern Box Deref

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Pattern Box Deref" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Pattern matching in Rust goes beyond simple value checks — it enables powerful dispatch mechanisms for type-safe command processing, visitor-pattern traversals, state machine transitions, and recursive data structure manipulation. Key difference from OCaml: 1. **Box deref**: Rust requires `Box<T>` for recursive types and Rust's patterns transparently deref through `Box`; OCaml's GC manages recursive variant pointers automatically.

Tutorial

The Problem

Pattern matching in Rust goes beyond simple value checks — it enables powerful dispatch mechanisms for type-safe command processing, visitor-pattern traversals, state machine transitions, and recursive data structure manipulation. This example demonstrates advanced pattern matching techniques that arise in compiler construction, game engines, protocol implementations, and functional programming idioms applied to real systems code.

🎯 Learning Outcomes

• Advanced pattern matching constructs specific to this example's domain

• How Rust's exhaustiveness checking prevents missed cases in complex dispatch

• How patterns interact with ownership — matching by value vs by reference

• How recursive enum patterns (trees, ASTs) work with variants

• Where this technique appears in real-world Rust: compilers, game engines, CLI tools

Code Example

// Box needed for recursive types
enum Tree {
    Leaf,
    Node { val: i32, left: Box<Tree>, right: Box<Tree> }
}

// Rust auto-derefs through Box in patterns
fn depth(t: &Tree) -> usize {
    match t {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => 
            1 + depth(left).max(depth(right)),
    }
}

(* GC handles allocation transparently *)
type tree = Leaf | Node of int * tree * tree

let rec depth = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + max (depth l) (depth r)

Key Differences

Box deref: Rust requires Box<T> for recursive types and Rust's patterns transparently deref through Box; OCaml's GC manages recursive variant pointers automatically.

Const patterns: Rust allows named const values in patterns; OCaml can use let open Consts in to bring constants into scope for pattern matching.

Visitor pattern: OCaml's idiomatic style uses recursive functions directly; Rust often uses both direct recursion and the trait-based visitor pattern for separation of concerns.

State machines: Both languages naturally express state machines with variant enums + match — this is one of the strongest arguments for algebraic types over OOP class hierarchies.

OCaml Approach

OCaml's ML heritage makes it the reference implementation for these patterns. Variant types, exhaustive matching, and recursive type handling in OCaml are equivalent in power:

(* Pattern matching in OCaml handles:
   - Variant constructors with data: Cmd (arg1, arg2) -> ...
   - Guards: | x when x > threshold -> ...  
   - Nested patterns: Node { left; right } -> ...
   - Recursive cases: the natural form for tree traversal *)

Full Source

#![allow(clippy::all)]
//! # Box Deref Patterns
//!
//! Pattern matching through Box with automatic dereferencing.

/// Binary search tree using Box for recursive structure.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree {
    Leaf,
    Node {
        val: i32,
        left: Box<Tree>,
        right: Box<Tree>,
    },
}

impl Tree {
    /// Create a leaf node.
    pub fn leaf() -> Box<Self> {
        Box::new(Tree::Leaf)
    }

    /// Create an internal node.
    pub fn node(val: i32, left: Box<Tree>, right: Box<Tree>) -> Box<Self> {
        Box::new(Tree::Node { val, left, right })
    }

    /// Create a single-node tree.
    pub fn singleton(val: i32) -> Box<Self> {
        Self::node(val, Self::leaf(), Self::leaf())
    }
}

/// Calculate tree depth - Rust auto-derefs through Box in patterns.
pub fn depth(t: &Tree) -> usize {
    match t {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => 1 + depth(left).max(depth(right)),
    }
}

/// Alternative using explicit deref.
pub fn depth_explicit(t: &Tree) -> usize {
    match t {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => {
            let l = depth_explicit(left.as_ref());
            let r = depth_explicit(right.as_ref());
            1 + l.max(r)
        }
    }
}

/// Check if tree contains a value (BST search).
pub fn contains(t: &Tree, v: i32) -> bool {
    match t {
        Tree::Leaf => false,
        Tree::Node { val, left, right } => match v.cmp(val) {
            std::cmp::Ordering::Equal => true,
            std::cmp::Ordering::Less => contains(left, v),
            std::cmp::Ordering::Greater => contains(right, v),
        },
    }
}

/// Insert a value into BST.
pub fn insert(t: Box<Tree>, v: i32) -> Box<Tree> {
    match *t {
        Tree::Leaf => Tree::singleton(v),
        Tree::Node { val, left, right } => {
            if v < val {
                Tree::node(val, insert(left, v), right)
            } else if v > val {
                Tree::node(val, left, insert(right, v))
            } else {
                Tree::node(val, left, right)
            }
        }
    }
}

/// Count total nodes in tree.
pub fn count(t: &Tree) -> usize {
    match t {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => 1 + count(left) + count(right),
    }
}

/// Sum all values in tree.
pub fn sum(t: &Tree) -> i32 {
    match t {
        Tree::Leaf => 0,
        Tree::Node { val, left, right } => val + sum(left) + sum(right),
    }
}

/// Collect values in order (inorder traversal).
pub fn inorder(t: &Tree) -> Vec<i32> {
    match t {
        Tree::Leaf => vec![],
        Tree::Node { val, left, right } => {
            let mut result = inorder(left);
            result.push(*val);
            result.extend(inorder(right));
            result
        }
    }
}

/// Find minimum value (leftmost).
pub fn min_value(t: &Tree) -> Option<i32> {
    match t {
        Tree::Leaf => None,
        Tree::Node { val, left, .. } => match left.as_ref() {
            Tree::Leaf => Some(*val),
            _ => min_value(left),
        },
    }
}

/// Find maximum value (rightmost).
pub fn max_value(t: &Tree) -> Option<i32> {
    match t {
        Tree::Leaf => None,
        Tree::Node { val, right, .. } => match right.as_ref() {
            Tree::Leaf => Some(*val),
            _ => max_value(right),
        },
    }
}

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

    fn build_tree(values: &[i32]) -> Box<Tree> {
        values.iter().fold(Tree::leaf(), |acc, &v| insert(acc, v))
    }

    #[test]
    fn test_depth_leaf() {
        assert_eq!(depth(&Tree::Leaf), 0);
    }

    #[test]
    fn test_depth_single() {
        let t = Tree::singleton(1);
        assert_eq!(depth(&t), 1);
    }

    #[test]
    fn test_depth_balanced() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(depth(&t), 3);
    }

    #[test]
    fn test_depth_approaches_equivalent() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(depth(&t), depth_explicit(&t));
    }

    #[test]
    fn test_contains() {
        let t = build_tree(&[5, 3, 7]);
        assert!(contains(&t, 3));
        assert!(contains(&t, 5));
        assert!(contains(&t, 7));
        assert!(!contains(&t, 6));
    }

    #[test]
    fn test_insert_maintains_bst() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        let values = inorder(&t);
        assert_eq!(values, vec![1, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_count() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(count(&t), 5);
    }

    #[test]
    fn test_sum() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(sum(&t), 20);
    }

    #[test]
    fn test_inorder() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(inorder(&t), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_min_max() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(min_value(&t), Some(1));
        assert_eq!(max_value(&t), Some(8));
    }

    #[test]
    fn test_min_max_empty() {
        assert_eq!(min_value(&Tree::Leaf), None);
        assert_eq!(max_value(&Tree::Leaf), None);
    }
}

(* OCaml trees — GC is transparent in patterns *)
type tree = Leaf | Node of int * tree * tree

let rec depth = function
  | Leaf -> 0
  | Node(_,l,r) -> 1 + max (depth l) (depth r)

let rec insert v = function
  | Leaf -> Node(v,Leaf,Leaf)
  | Node(x,l,r) when v<x -> Node(x, insert v l, r)
  | Node(x,l,r) when v>x -> Node(x, l, insert v r)
  | t -> t

let rec contains v = function
  | Leaf -> false
  | Node(x,_,_) when v=x  -> true
  | Node(x,l,_) when v<x  -> contains v l
  | Node(_,_,r)            -> contains v r

let () =
  let t = List.fold_left (fun a x->insert x a) Leaf [5;3;7;1;4] in
  Printf.printf "depth=%d\n" (depth t);
  Printf.printf "has 3=%b has 6=%b\n" (contains 3 t) (contains 6 t)

✓ Tests Rust test suite

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

    fn build_tree(values: &[i32]) -> Box<Tree> {
        values.iter().fold(Tree::leaf(), |acc, &v| insert(acc, v))
    }

    #[test]
    fn test_depth_leaf() {
        assert_eq!(depth(&Tree::Leaf), 0);
    }

    #[test]
    fn test_depth_single() {
        let t = Tree::singleton(1);
        assert_eq!(depth(&t), 1);
    }

    #[test]
    fn test_depth_balanced() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(depth(&t), 3);
    }

    #[test]
    fn test_depth_approaches_equivalent() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(depth(&t), depth_explicit(&t));
    }

    #[test]
    fn test_contains() {
        let t = build_tree(&[5, 3, 7]);
        assert!(contains(&t, 3));
        assert!(contains(&t, 5));
        assert!(contains(&t, 7));
        assert!(!contains(&t, 6));
    }

    #[test]
    fn test_insert_maintains_bst() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        let values = inorder(&t);
        assert_eq!(values, vec![1, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_count() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(count(&t), 5);
    }

    #[test]
    fn test_sum() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(sum(&t), 20);
    }

    #[test]
    fn test_inorder() {
        let t = build_tree(&[5, 3, 7, 1, 4]);
        assert_eq!(inorder(&t), vec![1, 3, 4, 5, 7]);
    }

    #[test]
    fn test_min_max() {
        let t = build_tree(&[5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(min_value(&t), Some(1));
        assert_eq!(max_value(&t), Some(8));
    }

    #[test]
    fn test_min_max_empty() {
        assert_eq!(min_value(&Tree::Leaf), None);
        assert_eq!(max_value(&Tree::Leaf), None);
    }
}

Deep Comparison

OCaml vs Rust: Box Deref Patterns

Recursive Tree Type

OCaml

(* GC handles allocation transparently *)
type tree = Leaf | Node of int * tree * tree

let rec depth = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + max (depth l) (depth r)

Rust

// Box needed for recursive types
enum Tree {
    Leaf,
    Node { val: i32, left: Box<Tree>, right: Box<Tree> }
}

// Rust auto-derefs through Box in patterns
fn depth(t: &Tree) -> usize {
    match t {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => 
            1 + depth(left).max(depth(right)),
    }
}

Key Insight: Auto-Deref

Rust automatically dereferences Box<T> to T in patterns:

// These are equivalent:
match t {
    Tree::Node { left, right, .. } => { /* left is &Box<Tree> */ }
}

match t {
    Tree::Node { left, right, .. } => { 
        depth(left)  // Works! Auto-deref to &Tree
    }
}

Insert Pattern

OCaml

let rec insert v = function
  | Leaf -> Node(v, Leaf, Leaf)
  | Node(x, l, r) when v < x -> Node(x, insert v l, r)
  | Node(x, l, r) when v > x -> Node(x, l, insert v r)
  | t -> t

Rust

fn insert(t: Box<Tree>, v: i32) -> Box<Tree> {
    match *t {  // Deref to move out of Box
        Tree::Leaf => Tree::singleton(v),
        Tree::Node { val, left, right } => {
            if v < val { Tree::node(val, insert(left, v), right) }
            else if v > val { Tree::node(val, left, insert(right, v)) }
            else { Tree::node(val, left, right) }
        }
    }
}

Key Differences

Aspect	OCaml	Rust
Memory	GC automatic	`Box<T>` explicit
Pattern match	Direct	Auto-deref through Box
Ownership	Implicit copy/share	Move or borrow
Recursive type	Direct	Requires indirection (Box)

Exercises

Extend the data type: Add a new variant or field to the main data structure and trace all the match expressions that need updating — practice the exhaustiveness feedback loop.

Accumulating visitor: Write a traversal function that collects all leaf values into a Vec<T> using only pattern matching and recursion.

State machine validation: Implement an invalid-transition error: when the state/event combination is unexpected, return Err("invalid transition") instead of panicking.

Open Source Repos

functional-rust

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

Rust