🎬 Pattern Matching Exhaustive match, destructuring, guards, let-else — compiler-verified branching.

📝 Text version (for readers / accessibility)

• match is exhaustive — the compiler ensures every variant is handled

• Destructuring extracts fields from structs, tuples, and enums in one step

• Guards (if conditions) add extra logic to match arms

• if let and let-else provide concise single-pattern matching

• Nested patterns and @ bindings handle complex data shapes elegantly

Example 1078: Visitor Pattern via Fold — Expression Evaluator

Difficulty: ⭐⭐ Category: Monadic Patterns / Higher-Order Functions OCaml Source: https://cs3110.github.io/textbook/chapters/interp/substitution.html

Problem Statement

Implement fold as a functional replacement for the visitor pattern. Define an expression tree and use fold to create both an evaluator and a pretty-printer without modifying the tree structure.

Learning Outcomes

Fold as the universal eliminator for algebraic data types
How closures replace the Visitor trait pattern in functional style
Box-based recursive enums in Rust vs OCaml's built-in recursive types
Multiple interpretations of the same data structure via different fold parameters

OCaml Approach

OCaml defines `fold` with labeled arguments (`~lit`, `~add`, `~mul`, `~neg`) — one function per variant. Creating new operations (eval, to_string) is just calling fold with different closures. No trait needed, no boilerplate.

Rust Approach

Rust uses `&dyn Fn` trait objects as parameters to fold, mirroring OCaml's approach. Helper constructors (`lit()`, `add()`) reduce the `Box::new` noise. A trait-based `ExprVisitor` is also shown for comparison with the OOP approach.

Key Differences

1. Labeled arguments: OCaml uses `~lit ~add ~mul ~neg`; Rust uses positional `&dyn Fn` parameters 2. Heap allocation: OCaml's recursive types are heap-allocated transparently; Rust needs explicit `Box<Expr>` 3. Visitor pattern: OCaml doesn't need it — fold is more natural. Rust can use either fold or a Visitor trait 4. Pattern matching: Both languages pattern match on the enum/variant; Rust requires `&` for references

#[derive(Debug, Clone)]
enum Expr {
    Lit(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Neg(Box<Expr>),
}

fn fold<R>(
    expr: &Expr,
    lit: &dyn Fn(f64) -> R,
    add: &dyn Fn(R, R) -> R,
    mul: &dyn Fn(R, R) -> R,
    neg: &dyn Fn(R) -> R,
) -> R {
    match expr {
        Expr::Lit(x) => lit(*x),
        Expr::Add(a, b) => add(fold(a, lit, add, mul, neg), fold(b, lit, add, mul, neg)),
        Expr::Mul(a, b) => mul(fold(a, lit, add, mul, neg), fold(b, lit, add, mul, neg)),
        Expr::Neg(a) => neg(fold(a, lit, add, mul, neg)),
    }
}

fn eval(expr: &Expr) -> f64 {
    fold(expr, &|x| x, &|a, b| a + b, &|a, b| a * b, &|x| -x)
}

fn to_string(expr: &Expr) -> String {
    fold(
        expr,
        &|x| format!("{x}"),
        &|a, b| format!("({a} + {b})"),
        &|a, b| format!("({a} * {b})"),
        &|a| format!("(-{a})"),
    )
}

fn lit(x: f64) -> Expr { Expr::Lit(x) }
fn add(a: Expr, b: Expr) -> Expr { Expr::Add(Box::new(a), Box::new(b)) }
fn mul(a: Expr, b: Expr) -> Expr { Expr::Mul(Box::new(a), Box::new(b)) }
fn neg(a: Expr) -> Expr { Expr::Neg(Box::new(a)) }

fn main() {
    let e = add(mul(lit(2.0), lit(3.0)), neg(lit(1.0)));
    println!("{} = {}", to_string(&e), eval(&e));
}

/* Output:
   ((2 * 3) + (-1)) = 5
*/

(* Visitor Pattern via Fold — Expression Evaluator *)

type expr =
  | Lit of float
  | Add of expr * expr
  | Mul of expr * expr
  | Neg of expr

let rec fold ~lit ~add ~mul ~neg = function
  | Lit x -> lit x
  | Add (a, b) -> add (fold ~lit ~add ~mul ~neg a) (fold ~lit ~add ~mul ~neg b)
  | Mul (a, b) -> mul (fold ~lit ~add ~mul ~neg a) (fold ~lit ~add ~mul ~neg b)
  | Neg a -> neg (fold ~lit ~add ~mul ~neg a)

let eval = fold ~lit:Fun.id ~add:(+.) ~mul:( *.) ~neg:(fun x -> -.x)

let to_string = fold
  ~lit:string_of_float
  ~add:(fun a b -> "(" ^ a ^ " + " ^ b ^ ")")
  ~mul:(fun a b -> "(" ^ a ^ " * " ^ b ^ ")")
  ~neg:(fun a -> "(-" ^ a ^ ")")

let () =
  let e = Add (Mul (Lit 2.0, Lit 3.0), Neg (Lit 1.0)) in
  assert (eval e = 5.0);
  assert (to_string e = "((2. * 3.) + (-1.))");
  Printf.printf "%s = %g\n" (to_string e) (eval e);
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Visitor Pattern via Fold

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

type expr =
| Lit of float
| Add of expr * expr
| Mul of expr * expr
| Neg of expr

let rec fold ~lit ~add ~mul ~neg = function
| Lit x -> lit x
| Add (a, b) -> add (fold ~lit ~add ~mul ~neg a) (fold ~lit ~add ~mul ~neg b)
| Mul (a, b) -> mul (fold ~lit ~add ~mul ~neg a) (fold ~lit ~add ~mul ~neg b)
| Neg a -> neg (fold ~lit ~add ~mul ~neg a)

let eval = fold ~lit:Fun.id ~add:(+.) ~mul:( *.) ~neg:(fun x -> -.x)

Rust (idiomatic)

pub fn fold<R>(
 expr: &Expr,
 lit: &dyn Fn(f64) -> R,
 add: &dyn Fn(R, R) -> R,
 mul: &dyn Fn(R, R) -> R,
 neg: &dyn Fn(R) -> R,
) -> R {
 match expr {
     Expr::Lit(x) => lit(*x),
     Expr::Add(a, b) => add(fold(a, lit, add, mul, neg), fold(b, lit, add, mul, neg)),
     Expr::Mul(a, b) => mul(fold(a, lit, add, mul, neg), fold(b, lit, add, mul, neg)),
     Expr::Neg(a) => neg(fold(a, lit, add, mul, neg)),
 }
}

pub fn eval(expr: &Expr) -> f64 {
 fold(expr, &|x| x, &|a, b| a + b, &|a, b| a * b, &|x| -x)
}

Rust (trait-based visitor)

pub trait ExprVisitor<R> {
 fn visit_lit(&self, x: f64) -> R;
 fn visit_add(&self, a: R, b: R) -> R;
 fn visit_mul(&self, a: R, b: R) -> R;
 fn visit_neg(&self, a: R) -> R;
}

Type Signatures

Concept	OCaml	Rust
Expression type	`type expr = Lit of float \	...`	`enum Expr { Lit(f64), ... }`
Fold signature	`val fold : lit:... -> add:... -> expr -> 'b`	`fn fold<R>(expr: &Expr, lit: &dyn Fn, ...) -> R`
Recursive boxing	Implicit (GC-managed)	`Box<Expr>` (explicit heap)
Labeled args	`~lit ~add ~mul ~neg`	Positional parameters

Key Insights

1. Fold IS the visitor pattern — OCaml developers never think "visitor pattern" because fold naturally provides the same capability. One function per variant, passed as closures. 2. Labeled arguments vs positional — OCaml's `~lit ~add ~mul ~neg` is self-documenting. Rust's positional `&dyn Fn` parameters require careful ordering or helper type aliases. 3. Box<Expr> is the price of no-GC — OCaml's recursive types just work. Rust needs `Box` to put recursive variants on the heap, adding syntactic noise. 4. Both share the core insight — data structure + multiple interpretations = fold with different closures. Neither OOP inheritance nor trait hierarchies needed. 5. Performance trade-off — Rust's `&dyn Fn` has dynamic dispatch overhead similar to OCaml's closures. For hot paths, Rust could use generics with `impl Fn` for monomorphization.

When to Use Each Style

Use fold (closure-based) when: You want maximum flexibility — new interpretations are just new sets of closures. Perfect for interpreters, pretty-printers, optimizers. Use trait-based visitor when: You want named, reusable visitor implementations that can carry state and be tested independently.