257 Intermediate

State Machine — Turnstile

State MachinesPattern Matching

Tutorial Video

Text description (accessibility)

This video demonstrates the "State Machine — Turnstile" functional Rust example. Difficulty level: Intermediate. Key concepts covered: State Machines, Pattern Matching. Model a turnstile that transitions between `Locked` and `Unlocked` states based on two events — inserting a `Coin` (unlock) or attempting a `Push` (lock if unlocked, stay if locked). Key difference from OCaml: 1. **Method vs free function:** OCaml `let transition state event = ...` is a free function; Rust `impl State { fn transition(self, ...) }` puts the behaviour on the type.

Tutorial

The Problem

Model a turnstile that transitions between Locked and Unlocked states based on two events — inserting a Coin (unlock) or attempting a Push (lock if unlocked, stay if locked).

🎯 Learning Outcomes

• How Rust enum variants map 1-to-1 to OCaml type constructors

• Using tuple patterns (self, event) in Rust match mirrors OCaml's tuple match syntax exactly

• Placing transition as a method on State vs. a free function — both are valid, method form is idiomatic Rust

• How Iterator::fold and Iterator::scan replace OCaml's List.fold_left for stateful iteration

🦀 The Rust Way

Rust encodes State and Event as enum types with #[derive(Debug, Clone, Copy, PartialEq, Eq)]. The transition logic lives as a method State::transition(self, event: Event) -> Self, keeping behaviour co-located with the type. The Copy bound means no ownership cost for passing states around.

Code Example

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State { Locked, Unlocked }

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event { Coin, Push }

impl State {
    pub fn transition(self, event: Event) -> Self {
        match (self, event) {
            (Self::Locked,   Event::Coin) => Self::Unlocked,
            (Self::Unlocked, Event::Push) => Self::Locked,
            (Self::Locked,   Event::Push) => Self::Locked,
            (Self::Unlocked, Event::Coin) => Self::Unlocked,
        }
    }

    pub fn name(self) -> &'static str {
        match self { Self::Locked => "Locked", Self::Unlocked => "Unlocked" }
    }
}

pub fn run_machine(initial: State, events: &[Event]) -> (State, Vec<(State, State)>) {
    let mut transitions = Vec::with_capacity(events.len());
    let final_state = events.iter().fold(initial, |s, &e| {
        let next = s.transition(e);
        transitions.push((s, next));
        next
    });
    (final_state, transitions)
}

type state = Locked | Unlocked
type event = Coin | Push

let transition state event = match state, event with
  | Locked, Coin -> Unlocked
  | Unlocked, Push -> Locked
  | Locked, Push -> Locked
  | Unlocked, Coin -> Unlocked

let state_name = function Locked -> "Locked" | Unlocked -> "Unlocked"

let () =
  let events = [Coin; Push; Push; Coin; Coin; Push] in
  let final = List.fold_left (fun s e ->
    let s' = transition s e in
    Printf.printf "%s -> %s\n" (state_name s) (state_name s');
    s'
  ) Locked events in
  Printf.printf "Final: %s\n" (state_name final)

Key Differences

Method vs free function: OCaml let transition state event = ... is a free function; Rust impl State { fn transition(self, ...) } puts the behaviour on the type.

Exhaustiveness: Both languages guarantee all arms are covered at compile time — OCaml via its type checker, Rust via the match exhaustiveness check.

Copy semantics: Rust's Copy trait lets State and Event be passed by value and used after — no equivalent concept in OCaml (all values are already value-or-pointer transparent).

Fold with side effects: OCaml's List.fold_left with Printf.printf inside the closure is a natural pattern; Rust separates concerns by collecting transitions first, then printing.

OCaml Approach

OCaml defines type state and type event as sum types, then writes transition as a free function matching on a (state, event) tuple. List.fold_left drives the simulation, threading state through each event.

Full Source

#![allow(clippy::all)]
// Example 257: State Machine — Turnstile
//
// A turnstile has two states (Locked, Unlocked) and two events (Coin, Push).
// OCaml encodes this with `type` declarations and a `match` on a tuple.
// Rust encodes it with `enum` + `impl` methods, giving the state machine
// behaviour directly on the type rather than as a free function.

// ---------------------------------------------------------------------------
// Solution 1: Idiomatic Rust — method on enum
//
// Defining `transition` as a method on `State` is idiomatic Rust:
// behaviour lives with the type.  The compiler exhaustively checks every
// (State, Event) combination at compile time — the same guarantee OCaml's
// pattern-match exhaustiveness check provides.
// ---------------------------------------------------------------------------

/// The two states a turnstile can be in.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State {
    Locked,
    Unlocked,
}

/// Events that can be applied to a turnstile.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event {
    Coin,
    Push,
}

impl State {
    /// Transition to the next state given an event.
    ///
    /// Mirrors the OCaml:
    ///   `let transition state event = match state, event with ...`
    ///
    /// Using `(self, event)` as the match discriminant mirrors OCaml's
    /// tuple pattern exactly.
    pub fn transition(self, event: Event) -> Self {
        match (self, event) {
            (Self::Locked, Event::Coin) => Self::Unlocked,
            (Self::Unlocked, Event::Push) => Self::Locked,
            // These arms keep the machine in its current state:
            (Self::Locked, Event::Push) => Self::Locked,
            (Self::Unlocked, Event::Coin) => Self::Unlocked,
        }
    }

    /// Human-readable name for display.
    pub fn name(self) -> &'static str {
        match self {
            Self::Locked => "Locked",
            Self::Unlocked => "Unlocked",
        }
    }
}

/// Run a sequence of events from `initial`, returning the final state.
/// Collects each (before, after) pair for inspection.
pub fn run_machine(initial: State, events: &[Event]) -> (State, Vec<(State, State)>) {
    let mut transitions = Vec::with_capacity(events.len());
    // Iterator fold mirrors OCaml's `List.fold_left`
    let final_state = events.iter().fold(initial, |s, &e| {
        let next = s.transition(e);
        transitions.push((s, next));
        next
    });
    (final_state, transitions)
}

// ---------------------------------------------------------------------------
// Solution 2: Functional style — free function mirrors OCaml directly
//
// OCaml uses a free `transition` function; this mirrors that style.
// In Rust, free functions and methods are equally idiomatic; here the
// free function makes the OCaml parallel explicit.
// ---------------------------------------------------------------------------

/// Free-function transition — mirrors OCaml's `let transition state event`.
pub fn transition(state: State, event: Event) -> State {
    state.transition(event)
}

/// Fold events over an initial state, collecting the trace.
/// Mirrors: `List.fold_left (fun s e -> transition s e) initial events`
pub fn fold_events(initial: State, events: &[Event]) -> Vec<State> {
    // `scan` is fold that yields every intermediate accumulator —
    // the functional equivalent of OCaml's fold with side-effecting printf.
    std::iter::once(initial)
        .chain(events.iter().scan(initial, |s, &e| {
            *s = transition(*s, e);
            Some(*s)
        }))
        .collect()
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    // -- Basic transition rules ---------------------------------------------

    #[test]
    fn test_locked_coin_unlocks() {
        assert_eq!(State::Locked.transition(Event::Coin), State::Unlocked);
    }

    #[test]
    fn test_unlocked_push_locks() {
        assert_eq!(State::Unlocked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_locked_push_stays_locked() {
        assert_eq!(State::Locked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_unlocked_coin_stays_unlocked() {
        assert_eq!(State::Unlocked.transition(Event::Coin), State::Unlocked);
    }

    // -- Sequence from the OCaml original: Coin Push Push Coin Coin Push ----

    #[test]
    fn test_ocaml_sequence_final_state() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (final_state, _) = run_machine(State::Locked, &events);
        assert_eq!(final_state, State::Locked);
    }

    #[test]
    fn test_ocaml_sequence_transitions() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (_, pairs) = run_machine(State::Locked, &events);
        // Locked→Unlocked, Unlocked→Locked, Locked→Locked,
        // Locked→Unlocked, Unlocked→Unlocked, Unlocked→Locked
        assert_eq!(
            pairs,
            vec![
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Locked),
                (State::Locked, State::Locked),
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Unlocked),
                (State::Unlocked, State::Locked),
            ]
        );
    }

    #[test]
    fn test_empty_sequence() {
        let (final_state, pairs) = run_machine(State::Locked, &[]);
        assert_eq!(final_state, State::Locked);
        assert!(pairs.is_empty());
    }

    #[test]
    fn test_fold_events_trace() {
        let events = [Event::Coin, Event::Push, Event::Push];
        let trace = fold_events(State::Locked, &events);
        assert_eq!(
            trace,
            vec![State::Locked, State::Unlocked, State::Locked, State::Locked,]
        );
    }

    #[test]
    fn test_free_transition_matches_method() {
        for &state in &[State::Locked, State::Unlocked] {
            for &event in &[Event::Coin, Event::Push] {
                assert_eq!(transition(state, event), state.transition(event));
            }
        }
    }

    #[test]
    fn test_state_names() {
        assert_eq!(State::Locked.name(), "Locked");
        assert_eq!(State::Unlocked.name(), "Unlocked");
    }
}

(* Example 257: State Machine — Turnstile *)
(* Encoding a finite state machine with algebraic types and pattern matching *)

(* Idiomatic OCaml — types and a transition function *)
type state = Locked | Unlocked
type event = Coin | Push

let transition state event = match state, event with
  | Locked, Coin -> Unlocked
  | Unlocked, Push -> Locked
  | Locked, Push -> Locked
  | Unlocked, Coin -> Unlocked

let state_name = function Locked -> "Locked" | Unlocked -> "Unlocked"

(* Recursive style — fold the event list, accumulating state *)
let rec run_machine state = function
  | [] -> state
  | event :: rest ->
    let next = transition state event in
    run_machine next rest

let () =
  (* Basic transition assertions *)
  assert (transition Locked Coin = Unlocked);
  assert (transition Unlocked Push = Locked);
  assert (transition Locked Push = Locked);
  assert (transition Unlocked Coin = Unlocked);

  (* OCaml sequence: Coin Push Push Coin Coin Push starting from Locked *)
  let events = [Coin; Push; Push; Coin; Coin; Push] in

  (* Print each step — mirrors the original snippet *)
  let _final = List.fold_left (fun s e ->
    let s' = transition s e in
    Printf.printf "%s -> %s\n" (state_name s) (state_name s');
    s'
  ) Locked events in

  (* Recursive version gives the same final state *)
  assert (run_machine Locked events = Locked);
  print_endline "ok"

✓ Tests Rust test suite

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

    // -- Basic transition rules ---------------------------------------------

    #[test]
    fn test_locked_coin_unlocks() {
        assert_eq!(State::Locked.transition(Event::Coin), State::Unlocked);
    }

    #[test]
    fn test_unlocked_push_locks() {
        assert_eq!(State::Unlocked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_locked_push_stays_locked() {
        assert_eq!(State::Locked.transition(Event::Push), State::Locked);
    }

    #[test]
    fn test_unlocked_coin_stays_unlocked() {
        assert_eq!(State::Unlocked.transition(Event::Coin), State::Unlocked);
    }

    // -- Sequence from the OCaml original: Coin Push Push Coin Coin Push ----

    #[test]
    fn test_ocaml_sequence_final_state() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (final_state, _) = run_machine(State::Locked, &events);
        assert_eq!(final_state, State::Locked);
    }

    #[test]
    fn test_ocaml_sequence_transitions() {
        let events = [
            Event::Coin,
            Event::Push,
            Event::Push,
            Event::Coin,
            Event::Coin,
            Event::Push,
        ];
        let (_, pairs) = run_machine(State::Locked, &events);
        // Locked→Unlocked, Unlocked→Locked, Locked→Locked,
        // Locked→Unlocked, Unlocked→Unlocked, Unlocked→Locked
        assert_eq!(
            pairs,
            vec![
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Locked),
                (State::Locked, State::Locked),
                (State::Locked, State::Unlocked),
                (State::Unlocked, State::Unlocked),
                (State::Unlocked, State::Locked),
            ]
        );
    }

    #[test]
    fn test_empty_sequence() {
        let (final_state, pairs) = run_machine(State::Locked, &[]);
        assert_eq!(final_state, State::Locked);
        assert!(pairs.is_empty());
    }

    #[test]
    fn test_fold_events_trace() {
        let events = [Event::Coin, Event::Push, Event::Push];
        let trace = fold_events(State::Locked, &events);
        assert_eq!(
            trace,
            vec![State::Locked, State::Unlocked, State::Locked, State::Locked,]
        );
    }

    #[test]
    fn test_free_transition_matches_method() {
        for &state in &[State::Locked, State::Unlocked] {
            for &event in &[Event::Coin, Event::Push] {
                assert_eq!(transition(state, event), state.transition(event));
            }
        }
    }

    #[test]
    fn test_state_names() {
        assert_eq!(State::Locked.name(), "Locked");
        assert_eq!(State::Unlocked.name(), "Unlocked");
    }
}

Deep Comparison

OCaml vs Rust: State Machine — Turnstile

Side-by-Side Code

OCaml

type state = Locked | Unlocked
type event = Coin | Push

let transition state event = match state, event with
  | Locked, Coin -> Unlocked
  | Unlocked, Push -> Locked
  | Locked, Push -> Locked
  | Unlocked, Coin -> Unlocked

let state_name = function Locked -> "Locked" | Unlocked -> "Unlocked"

let () =
  let events = [Coin; Push; Push; Coin; Coin; Push] in
  let final = List.fold_left (fun s e ->
    let s' = transition s e in
    Printf.printf "%s -> %s\n" (state_name s) (state_name s');
    s'
  ) Locked events in
  Printf.printf "Final: %s\n" (state_name final)

Rust (idiomatic — method on enum)

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum State { Locked, Unlocked }

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Event { Coin, Push }

impl State {
    pub fn transition(self, event: Event) -> Self {
        match (self, event) {
            (Self::Locked,   Event::Coin) => Self::Unlocked,
            (Self::Unlocked, Event::Push) => Self::Locked,
            (Self::Locked,   Event::Push) => Self::Locked,
            (Self::Unlocked, Event::Coin) => Self::Unlocked,
        }
    }

    pub fn name(self) -> &'static str {
        match self { Self::Locked => "Locked", Self::Unlocked => "Unlocked" }
    }
}

pub fn run_machine(initial: State, events: &[Event]) -> (State, Vec<(State, State)>) {
    let mut transitions = Vec::with_capacity(events.len());
    let final_state = events.iter().fold(initial, |s, &e| {
        let next = s.transition(e);
        transitions.push((s, next));
        next
    });
    (final_state, transitions)
}

Rust (functional style — free function mirrors OCaml)

pub fn transition(state: State, event: Event) -> State {
    state.transition(event)
}

/// Mirrors: List.fold_left (fun s e -> transition s e) initial events
/// scan yields every intermediate state, including the initial value.
pub fn fold_events(initial: State, events: &[Event]) -> Vec<State> {
    std::iter::once(initial)
        .chain(events.iter().scan(initial, |s, &e| {
            *s = transition(*s, e);
            Some(*s)
        }))
        .collect()
}

Type Signatures

Concept	OCaml	Rust
State type	`type state = Locked \\| Unlocked`	`enum State { Locked, Unlocked }`
Event type	`type event = Coin \\| Push`	`enum Event { Coin, Push }`
Transition	`val transition : state -> event -> state`	`fn transition(self, Event) -> Self`
Fold over events	`List.fold_left f initial events`	`events.iter().fold(initial, f)`
Scan with trace	`List.fold_left` + side effects	`Iterator::scan`
Copy value	implicit (OCaml values copied freely)	`#[derive(Clone, Copy)]` explicit

Key Insights

Tuple match syntax is identical: Both OCaml match state, event with and Rust match (self, event) destructure a pair of discriminants. The arm bodies differ only in syntax, not in logic.

Method vs free function: OCaml's free transition function is equally valid in Rust, but placing it as State::transition is idiomatic — behaviour lives with the type. Both forms appear in lib.rs to show the parallel.

**Copy eliminates borrowing ceremony:** Marking State and Event as Copy means every function can take values instead of references. No &State vs State decisions needed — the type is as cheap as an integer.

**scan is fold with observable intermediate states:** OCaml uses fold_left with printf inside the accumulator closure to observe each step. Rust's scan achieves the same: it threads mutable state through an iterator, yielding every intermediate value. once(initial).chain(scan(...)) produces the full trace including the starting state.

Exhaustiveness is guaranteed in both languages: The compiler verifies that every (State, Event) pair is handled. Adding a new variant to either enum immediately produces a compile error, making state machine evolution safe by construction.

When to Use Each Style

Use method-on-enum (idiomatic Rust) when: you want the transition logic discoverable through the type, benefit from IDE autocompletion on state., and prefer keeping related behaviour co-located with the data.

Use free-function style when: you are porting OCaml directly and want the parallel to remain visually obvious, or when the transition function needs to be passed as a first-class value (e.g., events.iter().fold(initial, |s, &e| transition(s, e))).

Exercises

Add an OutOfOrder state to the turnstile and transitions that enter and exit it, ensuring the state machine handles error recovery.

Model a vending machine as a state machine: states are the amount of money inserted and the selected item; transitions are coin insertion, item selection, and dispensing — enforce valid sequences at the type level.

Implement a stateful parser as a state machine that processes a stream of characters and recognizes a simple regular language (e.g., strings matching (a|b)*abb), returning Accept or Reject.

Open Source Repos

functional-rust

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

Rust