063 Intermediate

063 — Stack Module

Functional Programming

Tutorial

The Problem

A stack is a last-in, first-out (LIFO) data structure — one of the two fundamental abstractions alongside the queue. Stacks appear in function call management (the call stack), expression evaluation (operators and operands), undo/redo systems, DFS graph traversal, and balanced-parentheses checking (example 064). The stack abstraction — push, pop, peek, is_empty — hides implementation details from callers.

This example contrasts two implementations: a mutable stack (Stack<T> wrapping Vec) and an immutable persistent stack (FnStack<T> as a recursive enum). Persistent stacks are the default in OCaml; Rust typically uses mutable Vec-backed stacks for performance.

🎯 Learning Outcomes

• Implement a mutable stack using Vec with push, pop, peek, is_empty, size

• Implement an immutable persistent stack as a recursive enum (Cons list)

• Understand the trade-offs: mutable (O(1) amortized push/pop) vs persistent (O(1) push/pop, O(n) size)

• Use Option returns for safe pop and peek operations

• Recognize the Vec-backed stack as Rust idiom, the enum stack as functional idiom

• Back the Stack<T> with Vec<T> using push (O(1) amortized), pop (O(1)), and peek (O(1))

• Return Option<T> from pop and peek to handle empty-stack case without panicking

Code Example

#![allow(clippy::all)]
// 063: Stack Module
// Stack abstraction with struct + impl encapsulation

// Approach 1: Mutable stack wrapping Vec
#[derive(Debug)]
struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            elements: Vec::new(),
        }
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }

    fn push(&mut self, item: T) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.elements.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.elements.last()
    }

    fn size(&self) -> usize {
        self.elements.len()
    }
}

// Approach 2: Immutable (persistent) stack
#[derive(Debug, Clone)]
enum FnStack<T: Clone> {
    Empty,
    Cons(T, Box<FnStack<T>>),
}

impl<T: Clone> FnStack<T> {
    fn empty() -> Self {
        FnStack::Empty
    }

    fn is_empty(&self) -> bool {
        matches!(self, FnStack::Empty)
    }

    fn push(&self, item: T) -> Self {
        FnStack::Cons(item, Box::new(self.clone()))
    }

    fn pop(&self) -> Option<FnStack<T>> {
        match self {
            FnStack::Empty => None,
            FnStack::Cons(_, rest) => Some(*rest.clone()),
        }
    }

    fn peek(&self) -> Option<&T> {
        match self {
            FnStack::Empty => None,
            FnStack::Cons(x, _) => Some(x),
        }
    }
}

// Approach 3: From iterator
impl<T> FromIterator<T> for Stack<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Stack {
            elements: iter.into_iter().collect(),
        }
    }
}

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

    #[test]
    fn test_mutable_stack() {
        let mut s = Stack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.peek(), Some(&2));
    }

    #[test]
    fn test_immutable_stack() {
        let s = FnStack::empty().push(1).push(2).push(3);
        assert_eq!(s.peek(), Some(&3));
        let s2 = s.pop().unwrap();
        assert_eq!(s2.peek(), Some(&2));
        // Original unchanged
        assert_eq!(s.peek(), Some(&3));
    }

    #[test]
    fn test_from_iter() {
        let s: Stack<i32> = vec![1, 2, 3].into_iter().collect();
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
    }
}

(* 063: Stack Module *)
(* Functional stack with module encapsulation *)

(* Approach 1: Simple module *)
module Stack = struct
  type 'a t = 'a list

  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let pop = function
    | [] -> None
    | _ :: xs -> Some xs
  let peek = function
    | [] -> None
    | x :: _ -> Some x
  let size = List.length
  let to_list s = s
end

(* Approach 2: With signature hiding *)
module type STACK = sig
  type 'a t
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> 'a t option
  val peek : 'a t -> 'a option
  val size : 'a t -> int
end

module SafeStack : STACK = struct
  type 'a t = 'a list
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let pop = function [] -> None | _ :: xs -> Some xs
  let peek = function [] -> None | x :: _ -> Some x
  let size = List.length
end

(* Approach 3: Stack with fold *)
let stack_of_list lst =
  List.fold_left (fun s x -> Stack.push x s) Stack.empty lst

let stack_sum s =
  List.fold_left ( + ) 0 (Stack.to_list s)

(* Tests *)
let () =
  let s = Stack.empty in
  assert (Stack.is_empty s);
  let s = Stack.push 1 s in
  let s = Stack.push 2 s in
  let s = Stack.push 3 s in
  assert (not (Stack.is_empty s));
  assert (Stack.peek s = Some 3);
  assert (Stack.size s = 3);
  let s = match Stack.pop s with Some s -> s | None -> s in
  assert (Stack.peek s = Some 2);
  let s2 = stack_of_list [1; 2; 3] in
  assert (Stack.peek s2 = Some 3);
  assert (stack_sum s2 = 6);
  Printf.printf "✓ All tests passed\n"

Key Differences

List = persistent stack: OCaml's list is a persistent stack by construction. Prepending (x :: list) is O(1) and creates a new list sharing the old tail. Rust's Vec does not share structure.

Pop semantics: OCaml's functional pop returns (element, new_stack) as a pair since the stack is immutable. Rust's mutable Vec::pop() returns just the element, modifying the stack in place.

**Box for cons cell**: Rust's Cons(T, Box<FnStack<T>>) requires Box for the recursive type. OCaml's 'a list = [] | (::) of 'a * 'a list is built in.

Stack overflow: Deep OCaml lists can overflow the stack in recursive operations. Rust's Vec-based stack avoids recursion entirely.

**Vec as a stack:** Rust's Vec already supports stack operations: push (O(1) amortized), pop (O(1)), last (O(1) peek). OCaml's list is also naturally used as a stack with h :: t (push) and match l with h :: t -> ... (pop).

Module system: OCaml's module Stack = struct ... end encapsulates the stack implementation. Rust uses struct Stack<T> with an impl block — the same encapsulation, different syntax.

Error handling: pop and peek return Option<T> — safe, no panic. OCaml's match on an empty list raises Match_failure if not handled. Explicit None is safer than exceptions.

**Vec amortized push:** Vec::push is O(1) amortized — occasionally triggers a reallocation doubling the capacity. The Stack wrapper hides this detail. OCaml's list h :: t is always O(1) — no reallocation.

OCaml Approach

OCaml's functional stack is the list: type 'a stack = 'a list. push x s = x :: s, pop = function [] -> None | x :: t -> Some (x, t), peek = List.nth_opt s 0. The OCaml Stack module provides a mutable imperative stack like Rust's Vec-based version. Functional OCaml code normally just uses lists directly.

Full Source

#![allow(clippy::all)]
// 063: Stack Module
// Stack abstraction with struct + impl encapsulation

// Approach 1: Mutable stack wrapping Vec
#[derive(Debug)]
struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            elements: Vec::new(),
        }
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }

    fn push(&mut self, item: T) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.elements.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.elements.last()
    }

    fn size(&self) -> usize {
        self.elements.len()
    }
}

// Approach 2: Immutable (persistent) stack
#[derive(Debug, Clone)]
enum FnStack<T: Clone> {
    Empty,
    Cons(T, Box<FnStack<T>>),
}

impl<T: Clone> FnStack<T> {
    fn empty() -> Self {
        FnStack::Empty
    }

    fn is_empty(&self) -> bool {
        matches!(self, FnStack::Empty)
    }

    fn push(&self, item: T) -> Self {
        FnStack::Cons(item, Box::new(self.clone()))
    }

    fn pop(&self) -> Option<FnStack<T>> {
        match self {
            FnStack::Empty => None,
            FnStack::Cons(_, rest) => Some(*rest.clone()),
        }
    }

    fn peek(&self) -> Option<&T> {
        match self {
            FnStack::Empty => None,
            FnStack::Cons(x, _) => Some(x),
        }
    }
}

// Approach 3: From iterator
impl<T> FromIterator<T> for Stack<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Stack {
            elements: iter.into_iter().collect(),
        }
    }
}

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

    #[test]
    fn test_mutable_stack() {
        let mut s = Stack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.peek(), Some(&2));
    }

    #[test]
    fn test_immutable_stack() {
        let s = FnStack::empty().push(1).push(2).push(3);
        assert_eq!(s.peek(), Some(&3));
        let s2 = s.pop().unwrap();
        assert_eq!(s2.peek(), Some(&2));
        // Original unchanged
        assert_eq!(s.peek(), Some(&3));
    }

    #[test]
    fn test_from_iter() {
        let s: Stack<i32> = vec![1, 2, 3].into_iter().collect();
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
    }
}

(* 063: Stack Module *)
(* Functional stack with module encapsulation *)

(* Approach 1: Simple module *)
module Stack = struct
  type 'a t = 'a list

  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let pop = function
    | [] -> None
    | _ :: xs -> Some xs
  let peek = function
    | [] -> None
    | x :: _ -> Some x
  let size = List.length
  let to_list s = s
end

(* Approach 2: With signature hiding *)
module type STACK = sig
  type 'a t
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> 'a t option
  val peek : 'a t -> 'a option
  val size : 'a t -> int
end

module SafeStack : STACK = struct
  type 'a t = 'a list
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let pop = function [] -> None | _ :: xs -> Some xs
  let peek = function [] -> None | x :: _ -> Some x
  let size = List.length
end

(* Approach 3: Stack with fold *)
let stack_of_list lst =
  List.fold_left (fun s x -> Stack.push x s) Stack.empty lst

let stack_sum s =
  List.fold_left ( + ) 0 (Stack.to_list s)

(* Tests *)
let () =
  let s = Stack.empty in
  assert (Stack.is_empty s);
  let s = Stack.push 1 s in
  let s = Stack.push 2 s in
  let s = Stack.push 3 s in
  assert (not (Stack.is_empty s));
  assert (Stack.peek s = Some 3);
  assert (Stack.size s = 3);
  let s = match Stack.pop s with Some s -> s | None -> s in
  assert (Stack.peek s = Some 2);
  let s2 = stack_of_list [1; 2; 3] in
  assert (Stack.peek s2 = Some 3);
  assert (stack_sum s2 = 6);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_mutable_stack() {
        let mut s = Stack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.peek(), Some(&2));
    }

    #[test]
    fn test_immutable_stack() {
        let s = FnStack::empty().push(1).push(2).push(3);
        assert_eq!(s.peek(), Some(&3));
        let s2 = s.pop().unwrap();
        assert_eq!(s2.peek(), Some(&2));
        // Original unchanged
        assert_eq!(s.peek(), Some(&3));
    }

    #[test]
    fn test_from_iter() {
        let s: Stack<i32> = vec![1, 2, 3].into_iter().collect();
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Some(&3));
    }
}

Deep Comparison

Core Insight

A stack is LIFO (last in, first out). Both languages encapsulate the implementation: OCaml with module signatures, Rust with struct visibility. The functional stack uses a linked list; the Rust stack wraps Vec.

OCaml Approach

• Module with signature hiding internals

• Immutable stack using list (cons = push, tail = pop)

• push, pop, peek, is_empty operations

• Each operation returns a new stack (persistent)

Rust Approach

• struct Stack<T> { elements: Vec<T> } with private field

• impl Stack<T> with push, pop, peek

• Mutable methods modify in place

• Can also implement immutable version

Comparison Table

Feature	OCaml	Rust
Encapsulation	Module signature	Private fields
Push	`x :: stack` O(1)	`.push(x)` O(1) amortized
Pop	`List.tl stack`	`.pop()` → `Option<T>`
Peek	`List.hd stack`	`.last()` → `Option<&T>`
Mutability	Immutable (new stack)	Mutable in-place

Exercises

Two-stack queue: Implement a FIFO queue using two stacks (the classic interview question): one for enqueue, one for dequeue. Amortized O(1) per operation.

Expression evaluator: Write a postfix (RPN) expression evaluator using a Stack<f64>. Process "3 4 + 2 * 7 /" by pushing numbers and applying operators.

Linked stack iterator: Implement Iterator for FnStack<T: Clone> that yields each element from top to bottom. This requires traversing the linked list structure.

Min-stack: Implement a stack that tracks the minimum element in O(1) time by maintaining a parallel "min stack" — each push records the current minimum alongside the pushed value.

Stack-based evaluator: Use the Stack module to implement a reverse Polish notation (RPN) evaluator: evaluate(tokens: &[&str]) -> Result<i64, String> that handles numbers and operators +, -, *, /.

Open Source Repos

functional-rust

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

Rust