095 Intermediate

095 — Balanced Parentheses

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "095 — Balanced Parentheses" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Check whether a string of brackets is balanced: every opening bracket has a matching closing bracket in the correct order. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Check whether a string of brackets is balanced: every opening bracket has a matching closing bracket in the correct order. Implement both an imperative Vec stack version and a functional try_fold version. Compare with OCaml's recursive list-as-stack approach.

🎯 Learning Outcomes

• Use Vec<char> as an explicit stack for bracket matching

• Use stack.pop() != Some(expected) for match checking with early return

• Use try_fold to propagate failure: return None on mismatch, Some(stack) on success

• Understand try_fold as a short-circuiting fold returning Option

• Map Rust's Vec stack to OCaml's immutable list used as a stack

• Recognise the stack-based matching algorithm as the canonical solution

Code Example

pub fn is_balanced_fold(s: &str) -> bool {
    let result = s.chars().try_fold(Vec::new(), |mut stack, c| {
        match c {
            '(' | '[' | '{' => { stack.push(c); Some(stack) }
            ')' | ']' | '}' => {
                let exp = match c { ')'=>'(', ']'=>'[', '}'=>'{', _=>unreachable!() };
                if stack.pop() == Some(exp) { Some(stack) } else { None }
            }
            _ => Some(stack),
        }
    });
    matches!(result, Some(s) if s.is_empty())
}

let is_balanced s =
  let matching = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  let rec check stack i =
    if i = String.length s then stack = []
    else match s.[i] with
    | '(' | '[' | '{' as c -> check (c :: stack) (i + 1)
    | ')' | ']' | '}' as c ->
      (match stack with
       | top :: rest when top = matching c -> check rest (i + 1)
       | _ -> false)
    | _ -> check stack (i + 1)
  in check [] 0

Key Differences

Aspect	Rust	OCaml
Stack	`Vec<char>`	`char list`
Push	`stack.push(c)`	`c :: stack`
Pop	`stack.pop()`	Pattern `top :: rest`
Empty check	`stack.is_empty()`	`stack = []`
Functional style	`try_fold`	Tail recursion
Early exit	`return false`	Pattern match fails

The stack-based balanced bracket algorithm is O(n) time and O(n) space. The functional try_fold version is equivalent in complexity but more composable — the stack is the entire state, and failure is represented by None rather than an early return.

OCaml Approach

OCaml uses a recursive check stack i function. The matching helper maps closing brackets to their expected opening. The list stack top :: rest is pattern-matched, and recursion continues with rest when matched correctly. Lists serve as stacks naturally in OCaml — :: is O(1) push and pattern matching on top :: rest is O(1) pop.

Full Source

#![allow(clippy::all)]
//! # Balanced Parentheses
//!
//! Stack-based bracket matching. OCaml uses a list as a stack;
//! Rust uses `Vec<char>` the same way.

// ---------------------------------------------------------------------------
// Approach A: Imperative with Vec stack
// ---------------------------------------------------------------------------

pub fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '[' | '{' => stack.push(c),
            ')' | ']' | '}' => {
                let expected = match c {
                    ')' => '(',
                    ']' => '[',
                    '}' => '{',
                    _ => unreachable!(),
                };
                if stack.pop() != Some(expected) {
                    return false;
                }
            }
            _ => {}
        }
    }
    stack.is_empty()
}

// ---------------------------------------------------------------------------
// Approach B: Fold-based — functional style
// ---------------------------------------------------------------------------

pub fn is_balanced_fold(s: &str) -> bool {
    let result = s.chars().try_fold(Vec::new(), |mut stack, c| match c {
        '(' | '[' | '{' => {
            stack.push(c);
            Some(stack)
        }
        ')' | ']' | '}' => {
            let expected = match c {
                ')' => '(',
                ']' => '[',
                '}' => '{',
                _ => unreachable!(),
            };
            if stack.pop() == Some(expected) {
                Some(stack)
            } else {
                None
            }
        }
        _ => Some(stack),
    });
    matches!(result, Some(s) if s.is_empty())
}

// ---------------------------------------------------------------------------
// Approach C: Recursive — mirrors OCaml directly
// ---------------------------------------------------------------------------

pub fn is_balanced_recursive(s: &str) -> bool {
    fn check(chars: &[char], stack: &[char], i: usize) -> bool {
        if i == chars.len() {
            return stack.is_empty();
        }
        match chars[i] {
            '(' | '[' | '{' => {
                let mut new_stack = stack.to_vec();
                new_stack.push(chars[i]);
                check(chars, &new_stack, i + 1)
            }
            ')' | ']' | '}' => {
                let expected = match chars[i] {
                    ')' => '(',
                    ']' => '[',
                    '}' => '{',
                    _ => unreachable!(),
                };
                match stack.last() {
                    Some(&top) if top == expected => {
                        let new_stack = &stack[..stack.len() - 1];
                        check(chars, new_stack, i + 1)
                    }
                    _ => false,
                }
            }
            _ => check(chars, stack, i + 1),
        }
    }
    let chars: Vec<char> = s.chars().collect();
    check(&chars, &[], 0)
}

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

    #[test]
    fn test_balanced() {
        assert!(is_balanced("([]{})"));
        assert!(is_balanced("((()))"));
        assert!(is_balanced("[{()}]"));
    }

    #[test]
    fn test_unbalanced() {
        assert!(!is_balanced("([)]"));
        assert!(!is_balanced("("));
        assert!(!is_balanced(")"));
    }

    #[test]
    fn test_empty() {
        assert!(is_balanced(""));
    }

    #[test]
    fn test_with_other_chars() {
        assert!(is_balanced("(a + b) * [c - {d}]"));
    }

    #[test]
    fn test_fold_version() {
        assert!(is_balanced_fold("([]{})"));
        assert!(!is_balanced_fold("([)]"));
    }

    #[test]
    fn test_recursive_version() {
        assert!(is_balanced_recursive("([]{})"));
        assert!(!is_balanced_recursive("([)]"));
    }
}

let is_balanced s =
  let matching = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  let rec check stack i =
    if i = String.length s then stack = []
    else match s.[i] with
    | '(' | '[' | '{' as c -> check (c :: stack) (i + 1)
    | ')' | ']' | '}' as c ->
      (match stack with
       | top :: rest when top = matching c -> check rest (i + 1)
       | _ -> false)
    | _ -> check stack (i + 1)
  in
  check [] 0

let () =
  List.iter (fun s ->
    Printf.printf "%s: %b\n" s (is_balanced s)
  ) ["([]{})";"([)]";"((()))";"[{()}]";"("]

✓ Tests Rust test suite

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

    #[test]
    fn test_balanced() {
        assert!(is_balanced("([]{})"));
        assert!(is_balanced("((()))"));
        assert!(is_balanced("[{()}]"));
    }

    #[test]
    fn test_unbalanced() {
        assert!(!is_balanced("([)]"));
        assert!(!is_balanced("("));
        assert!(!is_balanced(")"));
    }

    #[test]
    fn test_empty() {
        assert!(is_balanced(""));
    }

    #[test]
    fn test_with_other_chars() {
        assert!(is_balanced("(a + b) * [c - {d}]"));
    }

    #[test]
    fn test_fold_version() {
        assert!(is_balanced_fold("([]{})"));
        assert!(!is_balanced_fold("([)]"));
    }

    #[test]
    fn test_recursive_version() {
        assert!(is_balanced_recursive("([]{})"));
        assert!(!is_balanced_recursive("([)]"));
    }
}

Deep Comparison

Comparison: Balanced Parentheses — OCaml vs Rust

Core Insight

Both languages model this as a stack problem. OCaml's list-as-stack is natural because lists are the primary data structure. Rust's Vec is the stack, with push/pop replacing cons/pattern-match. The key Rust addition is try_fold — a fold that can short-circuit on failure, combining functional style with early exit.

OCaml

let is_balanced s =
  let matching = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  let rec check stack i =
    if i = String.length s then stack = []
    else match s.[i] with
    | '(' | '[' | '{' as c -> check (c :: stack) (i + 1)
    | ')' | ']' | '}' as c ->
      (match stack with
       | top :: rest when top = matching c -> check rest (i + 1)
       | _ -> false)
    | _ -> check stack (i + 1)
  in check [] 0

Rust — try_fold

pub fn is_balanced_fold(s: &str) -> bool {
    let result = s.chars().try_fold(Vec::new(), |mut stack, c| {
        match c {
            '(' | '[' | '{' => { stack.push(c); Some(stack) }
            ')' | ']' | '}' => {
                let exp = match c { ')'=>'(', ']'=>'[', '}'=>'{', _=>unreachable!() };
                if stack.pop() == Some(exp) { Some(stack) } else { None }
            }
            _ => Some(stack),
        }
    });
    matches!(result, Some(s) if s.is_empty())
}

Comparison Table

Aspect	OCaml	Rust
Stack type	`char list` (immutable)	`Vec<char>` (mutable)
Push	`c :: stack`	`stack.push(c)`
Pop + check	`match stack with top :: rest when ...`	`stack.pop() == Some(expected)`
Early exit	Return `false` in recursion	`try_fold` returns `None`
Pattern matching	`as c` binds in or-pattern	Same syntax

Learner Notes

• **try_fold**: Rust's secret weapon — like fold but returns None/Err to stop early

• List vs Vec: OCaml's immutable list is safe but allocates on every push; Rust's Vec mutates in place

• **matches! macro**: Concise pattern matching for boolean checks — matches!(x, Some(s) if s.is_empty())

• Guard patterns: Both OCaml (when) and Rust (if) support guards in match arms

Exercises

Extend to also balance HTML-style tags: <div>…</div> where you must match tag names, not just single characters.

Return the position of the first unmatched bracket instead of just bool.

Handle nested string literals: brackets inside "…" should be ignored.

Implement balance_report(s: &str) -> (usize, usize) returning counts of unmatched opens and closes.

In OCaml, implement is_balanced using Seq.fold_left with an option char list accumulator.

Open Source Repos

functional-rust

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

Rust