🎬 Closures in Rust Fn/FnMut/FnOnce, capturing environment, move closures, higher-order functions.

📝 Text version (for readers / accessibility)

• Closures capture variables from their environment — by reference, mutable reference, or by value (move)

• Three traits: Fn (shared borrow), FnMut (mutable borrow), FnOnce (takes ownership)

• Higher-order functions like .map(), .filter(), .fold() accept closures as arguments

• move closures take ownership of captured variables — essential for threading

• Closures enable functional patterns: partial application, composition, and strategy

512: Closures as State Machine Transitions

Difficulty: 3 Level: Intermediate Encode automaton states as closures that return their own successor.

The Problem This Solves

A finite automaton has states and transitions. The naive approach is a loop over an enum with a match statement inside — functional but verbose, and the state logic is spread across a flat match. An alternative is to make each state a function (or closure) that consumes one input character and returns the next state. The "current state" is just the current closure. Transitioning is calling it. This pattern keeps state logic co-located: all the rules for `state_after_a` live in one place. It's easy to add states without touching others. And because Rust closures can capture mutable variables via `move`, you can build stateful recognizers that accumulate values or counters as they run — no separate state struct needed. The `make_lexer()` pattern in this example is the practical version: a single closure captures a mutable `LexState` enum, and each call advances the state. The closure is the state machine. Hand it characters, collect results.

The Intuition

Imagine each state as a room. You enter a room, show it a character, and it points you to the next room. The rooms are closures. Moving between rooms is calling the current closure with the next input. The machine has "accepted" when it lands in a room labeled "Accept." The stateful closure variant (`make_lexer`) is even simpler: there's one closure, it remembers where it is, and you just keep feeding it characters. State is hidden inside the closure's captured environment.

How It Works in Rust

1. State as closure — each state is a `fn(char) -> StateResult`; `StateResult::Continue(Box<dyn Fn(char) -> StateResult>)` carries the next state. 2. Fold over input — `chars.fold(initial_state, |state, c| match state { Continue(f) => f(c), other => other })` runs the machine. 3. Stateful closure — `make_lexer()` returns `impl FnMut(char) -> LexState`; the `LexState` is captured as a `move` variable and updated on each call. 4. `FnMut` for mutation — since the lexer writes to its captured state, it's `FnMut`, not `Fn`. 5. Acceptance check — after folding, check whether the final state is the accepted terminal state (`InB` for the `a*b+` pattern).

What This Unlocks

Build lexers and parsers where each state's logic is isolated in its own closure.
Compose state machines from smaller pieces — each state can delegate to sub-machines.
Carry accumulated output (tokens, counts) inside the closure's captured environment with no external state struct.

Key Differences

Concept	OCaml	Rust
State as function	Natural; functions are first-class	Same; closures are first-class, can capture mutable state
Recursive state types	`type state = char -> state` (with `rec`)	Must box: `Box<dyn Fn(char) -> StateResult>` — no recursive type alias
Stateful closures	Mutable closures via `ref` capture	`move` capture + `FnMut` for closures that mutate their environment
Fold-based automaton	`List.fold_left`	`Iterator::fold` — identical pattern

//! # 512. Closures as State Machine Transitions
//! Pattern: a*b+ — zero-or-more 'a' followed by one-or-more 'b'

/// Enum to represent state machine outputs
enum StateResult {
    Accept,
    Reject,
    Continue(Box<dyn Fn(char) -> StateResult>),
}

impl std::fmt::Debug for StateResult {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            StateResult::Accept => write!(f, "Accept"),
            StateResult::Reject => write!(f, "Reject"),
            StateResult::Continue(_) => write!(f, "Continue(<fn>)"),
        }
    }
}

/// State: start — expects 'a' or 'b'
fn state_start(c: char) -> StateResult {
    match c {
        'a' => StateResult::Continue(Box::new(state_after_a)),
        'b' => StateResult::Continue(Box::new(state_after_b)),
        _   => StateResult::Reject,
    }
}

/// State: seen at least one 'a', expecting more 'a' or 'b'
fn state_after_a(c: char) -> StateResult {
    match c {
        'a' => StateResult::Continue(Box::new(state_after_a)),
        'b' => StateResult::Continue(Box::new(state_after_b)),
        _   => StateResult::Reject,
    }
}

/// State: in 'b' sequence — only accepts more 'b'
fn state_after_b(c: char) -> StateResult {
    match c {
        'b' => StateResult::Continue(Box::new(state_after_b)),
        _   => StateResult::Reject,
    }
}

/// Run the state machine over an input string
/// Accept condition: ended in 'b' state (pattern: a*b+)
fn run_machine(input: &str) -> bool {
    let mut chars = input.chars();
    let first = match chars.next() {
        None => return false,
        Some(c) => c,
    };

    let initial = state_start(first);
    let final_state = chars.fold(initial, |state, c| {
        match state {
            StateResult::Continue(f) => f(c),
            other => other, // Reject stays Reject
        }
    });

    // Accept: we ended in the 'b' state — check via Continue(state_after_b)
    // Since we can't inspect closures, we track acceptance differently:
    // a*b+ is accepted if last char was 'b' and pattern was valid
    matches!(final_state, StateResult::Continue(_))
        && input.ends_with('b')
        && !matches!(final_state, StateResult::Reject)
}

/// Alternative: explicit state enum + closure transitions
#[derive(Clone, Debug, PartialEq)]
enum LexState { Start, InA, InB, Error }

fn make_lexer() -> impl FnMut(char) -> LexState {
    let mut state = LexState::Start;
    move |c: char| {
        state = match (&state, c) {
            (LexState::Start, 'a') => LexState::InA,
            (LexState::Start, 'b') => LexState::InB,
            (LexState::InA,   'a') => LexState::InA,
            (LexState::InA,   'b') => LexState::InB,
            (LexState::InB,   'b') => LexState::InB,
            _                      => LexState::Error,
        };
        state.clone()
    }
}

fn accepts_pattern(input: &str) -> bool {
    if input.is_empty() { return false; }
    let mut lexer = make_lexer();
    let last_state = input.chars().map(|c| lexer(c)).last();
    last_state == Some(LexState::InB)
}

fn main() {
    let tests = ["b", "ab", "aab", "abb", "aabb", "", "a", "ba", "abc", "bbb"];
    println!("Pattern: a*b+ (zero-or-more 'a', one-or-more 'b')");
    println!("{:<12} {:<12} {}", "Input", "Closure SM", "Enum SM");
    for s in &tests {
        println!("{:<12} {:<12} {}",
            format!("{:?}", s),
            run_machine(s),
            accepts_pattern(s));
    }

    // Demonstrate stateful lexer
    println!("\nStateful lexer trace of \"aabb\":");
    let mut lexer = make_lexer();
    for c in "aabb".chars() {
        println!("  '{}' -> {:?}", c, lexer(c));
    }
}

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

    #[test]
    fn test_accepts_pattern() {
        assert!(accepts_pattern("b"));
        assert!(accepts_pattern("ab"));
        assert!(accepts_pattern("aab"));
        assert!(accepts_pattern("abb"));
        assert!(accepts_pattern("bbb"));
    }

    #[test]
    fn test_rejects_pattern() {
        assert!(!accepts_pattern(""));
        assert!(!accepts_pattern("a"));
        assert!(!accepts_pattern("ba"));
        assert!(!accepts_pattern("abc"));
    }

    #[test]
    fn test_stateful_lexer() {
        let mut lex = make_lexer();
        assert_eq!(lex('a'), LexState::InA);
        assert_eq!(lex('b'), LexState::InB);
        assert_eq!(lex('b'), LexState::InB);
        assert_eq!(lex('a'), LexState::Error);
    }
}

(* State machine using closures in OCaml *)
(* Parsing a simple pattern: a*b+ (zero or more 'a', one or more 'b') *)

type result = Accept | Reject | Continue of (char -> result)

let rec state_start () : char -> result =
  fun c -> match c with
    | 'a' -> Continue (state_a ())
    | 'b' -> Continue (state_b ())
    | _   -> Reject

and state_a () : char -> result =
  fun c -> match c with
    | 'a' -> Continue (state_a ())
    | 'b' -> Continue (state_b ())
    | _   -> Reject

and state_b () : char -> result =
  fun c -> match c with
    | 'b' -> Continue (state_b ())
    | _   -> Reject

let run_machine input =
  let chars = List.of_seq (String.to_seq input) in
  match chars with
  | [] -> false  (* empty string doesn't match a*b+ *)
  | first :: rest ->
    let initial = state_start () first in
    let rec step state chars =
      match chars with
      | [] -> (match state with Accept -> true | Continue _ -> false | Reject -> false)
      | c :: cs ->
        match state with
        | Continue f -> step (f c) cs
        | Accept -> false
        | Reject -> false
    in
    (* Check if last state after processing all is Accept or we need final check *)
    let final_state = List.fold_left (fun st c ->
      match st with
      | Continue f -> f c
      | other -> other
    ) initial rest in
    match final_state with
    | Continue _ -> false  (* not in accept state at end *)
    | Accept -> true
    | Reject -> false

let () =
  let tests = ["b"; "ab"; "aab"; "abb"; "aabb"; ""; "a"; "ba"; "abc"] in
  List.iter (fun s ->
    Printf.printf "%S -> %b\n" s (run_machine s)
  ) tests