🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

095: Balanced Parentheses

Difficulty: 1 Level: Foundations Check whether every opening bracket has a matching close — using a stack.

The Problem This Solves

Compilers, linters, and code editors all need to verify bracket matching. When you type `([{}])` in an IDE and it highlights mismatches in real time, bracket checking is running on every keystroke. The core challenge: brackets must nest correctly. `([)]` fails even though both pairs exist — the nesting is wrong. You can't just count opens and closes; you need to remember which bracket you opened. A stack is the natural data structure: push when you open, pop and verify when you close. If the popped bracket doesn't match, fail immediately.

The Intuition

Imagine a stack of receipts. Every time you open a bracket, you place it on the pile. Every time you close a bracket, you check the top of the pile — it should be the matching opener. If the pile is empty at the end, everything balanced. `Vec<char>` in Rust works exactly like a stack: `.push(c)` to put something on top, `.pop()` to take it off. The `match` statement handles the three bracket pairs cleanly. The functional variant uses `try_fold` — it folds over the characters, threading the stack as accumulator, and returns `None` (early exit) on the first mismatch.

How It Works in Rust

pub fn is_balanced(s: &str) -> bool {
 let mut stack = Vec::new();
 for c in s.chars() {
     match c {
         '(' | '[' | '{' => stack.push(c),   // open: push
         ')' | ']' | '}' => {
             let expected = match c {
                 ')' => '(', ']' => '[', '}' => '{',
                 _ => unreachable!(),
             };
             if stack.pop() != Some(expected) {
                 return false;   // wrong or missing opener
             }
         }
         _ => {}  // ignore non-bracket characters
     }
 }
 stack.is_empty()  // true iff all openers were closed
}

The functional style uses `try_fold` for early exit:

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) }
         ')' | ']' | '}' => {
             // pop and verify — return None to short-circuit
             if stack.pop() == Some(matching(c)) { Some(stack) } else { None }
         }
         _ => Some(stack),
     }
 });
 matches!(result, Some(s) if s.is_empty())
}

`try_fold` stops as soon as `None` is returned — no wasted iterations.

What This Unlocks

Editor tooling — real-time bracket mismatch highlighting
Parser validation — pre-check input before handing it to a full parser
Config/data validation — check JSON, XML, TOML structure before parsing

Key Differences

Concept	OCaml	Rust
Stack type	`char list` (functional list)	`Vec<char>`
Push	`c :: stack` (prepend)	`stack.push(c)`
Pop	Pattern match on head	`stack.pop()` → `Option<char>`
Early exit	`Option` in recursive call	`try_fold` returning `None`
Mutual recursion	Natural with `let rec`	Simple loop — no recursion needed

//! # 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("([)]"));
    }
}

fn main() {
    println!("{:?}", is_balanced("([]{})"));
    println!("{:?}", is_balanced("((()))"));
    println!("{:?}", is_balanced("[{()}]"));
}

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)
  ) ["([]{})";"([)]";"((()))";"[{()}]";"("]

📊 Detailed 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

🐪 Show OCaml equivalent

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