059 Intermediate

Recursive Variant — Expression Tree

Algebraic Data Types

Tutorial Video

Text description (accessibility)

This video demonstrates the "Recursive Variant — Expression Tree" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Algebraic Data Types. Define a recursive algebraic data type for arithmetic expressions (Num, Add, Sub, Mul, Div). Key difference from OCaml: 1. **Box requirement:** Rust enums must have known size → recursive fields need `Box<T>` (heap indirection); OCaml allocates implicitly

Tutorial

The Problem

Define a recursive algebraic data type for arithmetic expressions (Num, Add, Sub, Mul, Div). Implement eval to compute the result and to_string to pretty-print with parentheses.

🎯 Learning Outcomes

• Model recursive data types in both languages

• Understand why Rust needs Box for recursive enums (known size requirement)

• Write structural recursion over tree-shaped data

• Add safe error handling for division by zero (Rust improvement)

• Use convenience constructors to reduce Box::new boilerplate

🦀 The Rust Way

Idiomatic: enum Expr with Box<Expr> for recursive fields, methods via impl

Free functions: Standalone eval() and to_string() mirroring OCaml

Safe division: eval_safe() returns Result<f64, String> for divide-by-zero

Code Example

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),  // etc.
}

impl Expr {
    pub fn new_add(l: Expr, r: Expr) -> Self {
        Expr::Add(Box::new(l), Box::new(r))
    }

    pub fn eval(&self) -> f64 {
        match self {
            Expr::Num(n)      => *n,
            Expr::Add(l, r)   => l.eval() + r.eval(),
            Expr::Mul(l, r)   => l.eval() * r.eval(),
            // ...
        }
    }
}

type expr =
  | Num of float
  | Add of expr * expr
  | Mul of expr * expr  (* etc. *)

let rec eval = function
  | Num n      -> n
  | Add (l, r) -> eval l +. eval r
  | Mul (l, r) -> eval l *. eval r
  (* ... *)

let rec to_string = function
  | Num n      -> string_of_float n
  | Add (l, r) -> Printf.sprintf "(%s + %s)" (to_string l) (to_string r)
  (* ... *)

Key Differences

Box requirement: Rust enums must have known size → recursive fields need Box<T> (heap indirection); OCaml allocates implicitly

Constructors: Rust benefits from helper functions (Expr::new_add(l, r)) to hide Box boilerplate; OCaml constructors work directly

Display trait: Rust's Display impl replaces OCaml's to_string function — enables format!("{expr}")

Error handling: Rust can return Result for safe division; OCaml's version silently produces infinity

Ownership in recursion: Rust's eval(&self) borrows the tree; OCaml pattern matching doesn't distinguish owned vs borrowed

**Recursive enum with Box:** Expr::Add(Box<Expr>, Box<Expr>) requires Box for the recursive self-reference. OCaml's type expr = Num of int | Add of expr * expr needs no annotation — GC handles heap allocation.

Interpreter pattern: eval is a structural recursive interpreter — the type of Expr directly shapes the recursion in eval. Each variant has one matching arm. This is the prototype for compiler backends and DSL interpreters.

**Box<Expr> construction:** Building trees requires explicit Box::new: Expr::Add(Box::new(Expr::Num(1)), Box::new(Expr::Num(2))). Helper constructors like add(l, r) hide this verbosity.

**Pattern matching on Box:** Matching on Box<T> requires box pattern syntax in nightly Rust, or deref coercion. Stable Rust matches &*left or uses if let to unbox.

OCaml Approach

OCaml's recursive variants are natural — type expr = Num of float | Add of expr * expr | ... — with no explicit heap allocation needed. Pattern matching destructures directly.

Full Source

#![allow(clippy::all)]
//! # Recursive Variant — Expression Tree
//!
//! OCaml's recursive variants with payloads map to Rust's `enum` with
//! `Box`-wrapped recursive fields. The key difference: Rust requires
//! explicit heap allocation (`Box`) for recursive types because it must
//! know the size of every type at compile time.

// ---------------------------------------------------------------------------
// Approach A: Idiomatic Rust — enum with Box, methods via impl
// ---------------------------------------------------------------------------

/// An arithmetic expression tree.
///
/// `Box<Expr>` is required because `Expr` is recursive — without it,
/// `Expr` would have infinite size. OCaml handles this implicitly because
/// all variant payloads are heap-allocated.
#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
}

/// Convenience constructors to avoid writing `Box::new(...)` everywhere.
/// This is a common Rust pattern for recursive data structures.
impl Expr {
    pub fn num(n: f64) -> Self {
        Expr::Num(n)
    }

    pub fn new_add(l: Expr, r: Expr) -> Self {
        Expr::Add(Box::new(l), Box::new(r))
    }

    pub fn new_sub(l: Expr, r: Expr) -> Self {
        Expr::Sub(Box::new(l), Box::new(r))
    }

    pub fn new_mul(l: Expr, r: Expr) -> Self {
        Expr::Mul(Box::new(l), Box::new(r))
    }

    pub fn new_div(l: Expr, r: Expr) -> Self {
        Expr::Div(Box::new(l), Box::new(r))
    }
}

impl Expr {
    /// Evaluate the expression tree recursively.
    ///
    /// Mirrors OCaml's `eval` function — structural recursion over the variant.
    /// Takes `&self` (borrowed reference) rather than consuming the tree.
    pub fn eval(&self) -> f64 {
        match self {
            Expr::Num(n) => *n,
            Expr::Add(l, r) => l.eval() + r.eval(),
            Expr::Sub(l, r) => l.eval() - r.eval(),
            Expr::Mul(l, r) => l.eval() * r.eval(),
            Expr::Div(l, r) => l.eval() / r.eval(),
        }
    }
}

/// Display produces the same parenthesized format as OCaml's `to_string`.
impl std::fmt::Display for Expr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Expr::Num(n) => write!(f, "{n}"),
            Expr::Add(l, r) => write!(f, "({l} + {r})"),
            Expr::Sub(l, r) => write!(f, "({l} - {r})"),
            Expr::Mul(l, r) => write!(f, "({l} * {r})"),
            Expr::Div(l, r) => write!(f, "({l} / {r})"),
        }
    }
}

// ---------------------------------------------------------------------------
// Approach B: Free functions — closer to OCaml style
// ---------------------------------------------------------------------------

/// Evaluate as a standalone function (OCaml style).
pub fn eval(expr: &Expr) -> f64 {
    expr.eval()
}

/// Convert to string as a standalone function.
pub fn to_string(expr: &Expr) -> String {
    format!("{expr}")
}

// ---------------------------------------------------------------------------
// Approach C: Safe division with Result
// ---------------------------------------------------------------------------

/// Division-safe evaluation that returns an error on divide-by-zero
/// instead of producing `inf` or `NaN`.
///
/// This is a Rust improvement over the OCaml version — OCaml's version
/// silently produces `infinity` on division by zero.
pub fn eval_safe(expr: &Expr) -> Result<f64, String> {
    match expr {
        Expr::Num(n) => Ok(*n),
        Expr::Add(l, r) => Ok(eval_safe(l)? + eval_safe(r)?),
        Expr::Sub(l, r) => Ok(eval_safe(l)? - eval_safe(r)?),
        Expr::Mul(l, r) => Ok(eval_safe(l)? * eval_safe(r)?),
        Expr::Div(l, r) => {
            let divisor = eval_safe(r)?;
            if divisor == 0.0 {
                Err(format!("Division by zero: {expr}"))
            } else {
                Ok(eval_safe(l)? / divisor)
            }
        }
    }
}

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

    // (1 + 2) * (10 - 4) = 18
    fn sample_expr() -> Expr {
        Expr::new_mul(
            Expr::new_add(Expr::num(1.0), Expr::num(2.0)),
            Expr::new_sub(Expr::num(10.0), Expr::num(4.0)),
        )
    }

    #[test]
    fn test_eval_basic() {
        assert!((sample_expr().eval() - 18.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_eval_single_num() {
        assert!((Expr::num(42.0).eval() - 42.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_display() {
        assert_eq!(to_string(&sample_expr()), "((1 + 2) * (10 - 4))");
    }

    #[test]
    fn test_eval_nested_division() {
        // 10 / (5 - 3) = 5
        let e = Expr::new_div(
            Expr::num(10.0),
            Expr::new_sub(Expr::num(5.0), Expr::num(3.0)),
        );
        assert!((e.eval() - 5.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_eval_safe_division_by_zero() {
        let e = Expr::new_div(Expr::num(1.0), Expr::num(0.0));
        assert!(eval_safe(&e).is_err());
    }

    #[test]
    fn test_eval_safe_ok() {
        assert!((eval_safe(&sample_expr()).unwrap() - 18.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_display_num() {
        assert_eq!(format!("{}", Expr::num(3.14)), "3.14");
    }

    #[test]
    fn test_clone_and_eq() {
        let e = sample_expr();
        let e2 = e.clone();
        assert_eq!(e, e2);
    }
}

(* Recursive Variant — Expression Tree *)

type expr =
  | Num of float
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr

(* Implementation 1: Direct recursive eval *)
let rec eval = function
  | Num n         -> n
  | Add (l, r)    -> eval l +. eval r
  | Sub (l, r)    -> eval l -. eval r
  | Mul (l, r)    -> eval l *. eval r
  | Div (l, r)    -> eval l /. eval r

(* Implementation 2: to_string with parentheses *)
let rec to_string = function
  | Num n         -> string_of_float n
  | Add (l, r)    -> Printf.sprintf "(%s + %s)" (to_string l) (to_string r)
  | Sub (l, r)    -> Printf.sprintf "(%s - %s)" (to_string l) (to_string r)
  | Mul (l, r)    -> Printf.sprintf "(%s * %s)" (to_string l) (to_string r)
  | Div (l, r)    -> Printf.sprintf "(%s / %s)" (to_string l) (to_string r)

(* Tests *)
let () =
  (* (1 + 2) * (10 - 4) = 18 *)
  let e = Mul (Add (Num 1., Num 2.), Sub (Num 10., Num 4.)) in
  assert (eval e = 18.);
  assert (eval (Num 42.) = 42.);
  assert (eval (Div (Num 10., Sub (Num 5., Num 3.))) = 5.);
  Printf.printf "%s = %.1f\n" (to_string e) (eval e);
  Printf.printf "All expression-tree tests passed!\n"

✓ Tests Rust test suite

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

    // (1 + 2) * (10 - 4) = 18
    fn sample_expr() -> Expr {
        Expr::new_mul(
            Expr::new_add(Expr::num(1.0), Expr::num(2.0)),
            Expr::new_sub(Expr::num(10.0), Expr::num(4.0)),
        )
    }

    #[test]
    fn test_eval_basic() {
        assert!((sample_expr().eval() - 18.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_eval_single_num() {
        assert!((Expr::num(42.0).eval() - 42.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_display() {
        assert_eq!(to_string(&sample_expr()), "((1 + 2) * (10 - 4))");
    }

    #[test]
    fn test_eval_nested_division() {
        // 10 / (5 - 3) = 5
        let e = Expr::new_div(
            Expr::num(10.0),
            Expr::new_sub(Expr::num(5.0), Expr::num(3.0)),
        );
        assert!((e.eval() - 5.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_eval_safe_division_by_zero() {
        let e = Expr::new_div(Expr::num(1.0), Expr::num(0.0));
        assert!(eval_safe(&e).is_err());
    }

    #[test]
    fn test_eval_safe_ok() {
        assert!((eval_safe(&sample_expr()).unwrap() - 18.0).abs() < f64::EPSILON);
    }

    #[test]
    fn test_display_num() {
        assert_eq!(format!("{}", Expr::num(3.14)), "3.14");
    }

    #[test]
    fn test_clone_and_eq() {
        let e = sample_expr();
        let e2 = e.clone();
        assert_eq!(e, e2);
    }
}

Deep Comparison

Comparison: Expression Tree — OCaml vs Rust

OCaml

type expr =
  | Num of float
  | Add of expr * expr
  | Mul of expr * expr  (* etc. *)

let rec eval = function
  | Num n      -> n
  | Add (l, r) -> eval l +. eval r
  | Mul (l, r) -> eval l *. eval r
  (* ... *)

let rec to_string = function
  | Num n      -> string_of_float n
  | Add (l, r) -> Printf.sprintf "(%s + %s)" (to_string l) (to_string r)
  (* ... *)

Rust — Idiomatic (Box + impl)

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),  // etc.
}

impl Expr {
    pub fn new_add(l: Expr, r: Expr) -> Self {
        Expr::Add(Box::new(l), Box::new(r))
    }

    pub fn eval(&self) -> f64 {
        match self {
            Expr::Num(n)      => *n,
            Expr::Add(l, r)   => l.eval() + r.eval(),
            Expr::Mul(l, r)   => l.eval() * r.eval(),
            // ...
        }
    }
}

Rust — Safe Division (Result)

pub fn eval_safe(expr: &Expr) -> Result<f64, String> {
    match expr {
        Expr::Div(l, r) => {
            let divisor = eval_safe(r)?;
            if divisor == 0.0 { Err("Division by zero".into()) }
            else { Ok(eval_safe(l)? / divisor) }
        }
        // ...
    }
}

Comparison Table

Aspect	OCaml	Rust
Recursive type	`type expr = Num of float \\| Add of expr * expr`	`enum Expr { Num(f64), Add(Box<Expr>, Box<Expr>) }`
Heap allocation	Implicit (GC-managed)	Explicit with `Box<T>`
Constructor	`Add (l, r)` directly	`Expr::Add(Box::new(l), Box::new(r))` or helper
Pattern matching	`\\| Add (l, r) -> ...`	`Expr::Add(l, r) => ...` (l, r are `&Box<Expr>`)
Float ops	`+.` `-` `.` `/.` (separate from int)	`+` `-` `*` `/` (overloaded via traits)
Division safety	Returns `infinity`	Can return `Result` with error
Pretty-print	Custom `to_string` function	`impl Display` trait

Type Signatures Explained

OCaml: val eval : expr -> float — takes an expression, returns a float. The recursive structure is handled by the GC.

Rust: fn eval(&self) -> f64 — borrows self (&Expr). When matching Add(l, r), l and r are &Box<Expr>, which auto-derefs to &Expr for the recursive call.

Takeaways

Box is the price of ownership: OCaml's GC handles recursive types transparently; Rust makes heap allocation explicit

Constructor boilerplate: Helper functions like new_add() are a common Rust pattern to hide Box::new

Safety upgrade: Rust's Result type makes error handling for division explicit and composable with ?

Display trait integrates with format!, println!, and to_string() automatically

Auto-deref makes working with Box<Expr> ergonomic — you rarely notice the indirection in pattern matching

Exercises

Add a Let { name: String, value: Box<Expr>, body: Box<Expr> } variant to the expression tree and extend the evaluator to handle variable binding with a simple environment map.

Implement a pretty-printer for the expression tree that adds parentheses only where needed based on operator precedence.

Write a fold_expr function analogous to fold on lists, and use it to implement both evaluation and pretty-printing without writing recursive match in each function.

Variables: Add Expr::Var(String) variant and implement eval_with_env(expr: &Expr, env: &HashMap<String, i64>) -> Option<i64> that looks up variables in an environment, returning None for unbound variables.

Pretty printer: Implement a pretty-printer that produces minimal parentheses — only add parentheses when operator precedence requires them. Add(Mul(2, 3), 4) should print as 2 * 3 + 4 not (2 * 3) + 4.

Open Source Repos

functional-rust

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

Rust