1002 Intermediate

Stack Module with Signature

Functional Programming

Tutorial

The Problem

Implement a persistent functional stack: a LIFO data structure where push and pop return entirely new stack values rather than mutating in place. The OCaml original uses a module signature (STACK) and a list-backed implementation (ListStack) to show how interface and implementation are separated. The Rust version models the same contract using a consuming-method API on a concrete struct, demonstrating how OCaml-style module signatures translate into Rust's type system. The goal is to understand both the structural equivalence and the differences in how each language expresses abstraction and error handling.

🎯 Learning Outcomes

• How OCaml module signatures (module type STACK) translate to Rust structs with well-defined consuming-method APIs

• Why consuming self by value (push(self, x) -> Self, pop(self) -> Result<Self, Empty>) achieves a logically persistent interface in Rust

• How method chaining (Stack::empty().push(1).push(2).push(3)) mirrors OCaml's pipeline operator style (empty |> push 1 |> push 2 |> push 3)

• How OCaml's exception Empty maps to Rust's Result<_, Empty>, making the empty-stack error case explicit and statically checked

• Why Rust encodes the module-signature contract as inherent methods rather than a trait, and when a trait would be more appropriate

Code Example

#[derive(Debug, Clone, PartialEq)]
pub struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    pub fn empty() -> Self { Stack { items: Vec::new() } }

    /// Push consumes self and returns the new stack (persistent-style API)
    pub fn push(mut self, x: T) -> Self {
        self.items.push(x);
        self
    }

    pub fn peek(&self) -> Result<&T, Empty> {
        self.items.last().ok_or(Empty)
    }

    pub fn pop(mut self) -> Result<Self, Empty> {
        if self.items.is_empty() { Err(Empty) }
        else { self.items.pop(); Ok(self) }
    }
}

module type STACK = sig
  type 'a t
  exception Empty
  val empty    : 'a t
  val is_empty : 'a t -> bool
  val push     : 'a -> 'a t -> 'a t
  val peek     : 'a t -> 'a      (* raises Empty *)
  val pop      : 'a t -> 'a t    (* raises Empty *)
  val size     : 'a t -> int
end

module ListStack : STACK = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop  = function [] -> raise Empty | _ :: s  -> s
end

(* Usage: pipeline operator with push *)
let s = ListStack.(empty |> push 1 |> push 2 |> push 3)

Key Differences

Error handling: OCaml raises Empty as an exception that callers may or may not catch; Rust returns Result<_, Empty>, making the error branch statically visible in every call site's type

Abstraction mechanism: OCaml uses a module signature to seal the implementation type; Rust makes items: Vec<T> a private field — callers cannot see the backing store without a trait

Persistence semantics: OCaml's list prepend is inherently persistent and O(1); Rust's Vec-backed version mutates in place under a consuming interface, giving the appearance of persistence while reusing memory

Interface definition: OCaml separates signature (STACK) from implementation (ListStack) explicitly; Rust combines both in the impl Stack<T> block, relying on field privacy for encapsulation

OCaml Approach

OCaml defines the STACK module signature with a polymorphic type 'a t, an Empty exception, and five operations: empty, is_empty, push, peek, and pop. ListStack implements this signature using an 'a list as the backing store: push x s = x :: s (O(1) prepend), pop = List.tl, peek = List.hd. Both peek and pop raise the Empty exception on an empty list. The signature seals the implementation — callers cannot observe that the stack is a list. The pipeline operator |> makes construction read left-to-right: empty |> push 1 |> push 2.

Full Source

#![allow(clippy::all)]
//! Stack Module with Signature
//! See example.ml for OCaml reference
//!
//! Mirrors OCaml's `ListStack` module: push/pop consume and return a new stack,
//! giving a persistent, functional interface over a `Vec` backbone.

#[derive(Debug, Clone, PartialEq)]
pub struct Stack<T> {
    items: Vec<T>,
}

#[derive(Debug, PartialEq)]
pub struct Empty;

impl<T> Stack<T> {
    /// The empty stack.
    pub fn empty() -> Self {
        Stack { items: Vec::new() }
    }

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

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

    /// Push an element, returning the new stack (consuming `self`).
    pub fn push(mut self, x: T) -> Self {
        self.items.push(x);
        self
    }

    /// Return a reference to the top element without removing it.
    pub fn peek(&self) -> Result<&T, Empty> {
        self.items.last().ok_or(Empty)
    }

    /// Remove the top element, returning the remainder (consuming `self`).
    pub fn pop(mut self) -> Result<Self, Empty> {
        if self.items.is_empty() {
            Err(Empty)
        } else {
            self.items.pop();
            Ok(self)
        }
    }
}

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

    #[test]
    fn test_empty() {
        let s: Stack<i32> = Stack::empty();
        assert!(s.is_empty());
        assert_eq!(s.size(), 0);
    }

    #[test]
    fn test_push_peek_size() {
        let s = Stack::empty().push(1).push(2).push(3);
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Ok(&3));
        assert!(!s.is_empty());
    }

    #[test]
    fn test_pop() {
        let s = Stack::empty().push(1).push(2).push(3);
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&2));
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&1));
        let s = s.pop().unwrap();
        assert!(s.is_empty());
    }

    #[test]
    fn test_peek_empty_err() {
        let s: Stack<i32> = Stack::empty();
        assert_eq!(s.peek(), Err(Empty));
    }

    #[test]
    fn test_pop_empty_err() {
        let s: Stack<i32> = Stack::empty();
        assert!(s.pop().is_err());
    }

    #[test]
    fn test_pipeline_style() {
        // Mirror OCaml: empty |> push 1 |> push 2 |> push 3
        let s = Stack::empty().push(1).push(2).push(3);
        assert_eq!(s.peek(), Ok(&3));
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&2));
    }
}

module type STACK = sig
  type 'a t
  exception Empty

  val empty    : 'a t
  val is_empty : 'a t -> bool
  val push     : 'a -> 'a t -> 'a t
  val peek     : 'a t -> 'a      (* raises Empty *)
  val pop      : 'a t -> 'a t    (* raises Empty *)
  val size     : 'a t -> int
end

module ListStack : STACK = struct
  type 'a t = 'a list
  exception Empty

  let empty        = []
  let is_empty s   = s = []
  let push x s     = x :: s
  let size s       = List.length s

  let peek = function
    | []     -> raise Empty
    | x :: _ -> x

  let pop = function
    | []      -> raise Empty
    | _ :: s  -> s
end

let () =
  let open ListStack in
  let s = empty |> push 1 |> push 2 |> push 3 in
  Printf.printf "size = %d\n" (size s);
  Printf.printf "peek = %d\n" (peek s);
  let s' = pop s in
  Printf.printf "after pop, peek = %d\n" (peek s')

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        let s: Stack<i32> = Stack::empty();
        assert!(s.is_empty());
        assert_eq!(s.size(), 0);
    }

    #[test]
    fn test_push_peek_size() {
        let s = Stack::empty().push(1).push(2).push(3);
        assert_eq!(s.size(), 3);
        assert_eq!(s.peek(), Ok(&3));
        assert!(!s.is_empty());
    }

    #[test]
    fn test_pop() {
        let s = Stack::empty().push(1).push(2).push(3);
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&2));
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&1));
        let s = s.pop().unwrap();
        assert!(s.is_empty());
    }

    #[test]
    fn test_peek_empty_err() {
        let s: Stack<i32> = Stack::empty();
        assert_eq!(s.peek(), Err(Empty));
    }

    #[test]
    fn test_pop_empty_err() {
        let s: Stack<i32> = Stack::empty();
        assert!(s.pop().is_err());
    }

    #[test]
    fn test_pipeline_style() {
        // Mirror OCaml: empty |> push 1 |> push 2 |> push 3
        let s = Stack::empty().push(1).push(2).push(3);
        assert_eq!(s.peek(), Ok(&3));
        let s = s.pop().unwrap();
        assert_eq!(s.peek(), Ok(&2));
    }
}

Deep Comparison

OCaml vs Rust: Stack Module with Signature

Side-by-Side Code

OCaml

module type STACK = sig
  type 'a t
  exception Empty
  val empty    : 'a t
  val is_empty : 'a t -> bool
  val push     : 'a -> 'a t -> 'a t
  val peek     : 'a t -> 'a      (* raises Empty *)
  val pop      : 'a t -> 'a t    (* raises Empty *)
  val size     : 'a t -> int
end

module ListStack : STACK = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop  = function [] -> raise Empty | _ :: s  -> s
end

(* Usage: pipeline operator with push *)
let s = ListStack.(empty |> push 1 |> push 2 |> push 3)

Rust (idiomatic)

#[derive(Debug, Clone, PartialEq)]
pub struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    pub fn empty() -> Self { Stack { items: Vec::new() } }

    /// Push consumes self and returns the new stack (persistent-style API)
    pub fn push(mut self, x: T) -> Self {
        self.items.push(x);
        self
    }

    pub fn peek(&self) -> Result<&T, Empty> {
        self.items.last().ok_or(Empty)
    }

    pub fn pop(mut self) -> Result<Self, Empty> {
        if self.items.is_empty() { Err(Empty) }
        else { self.items.pop(); Ok(self) }
    }
}

Rust (functional/recursive)

// Recursive push on an immutable-style linked-list stack
pub enum ListStack<T> {
    Nil,
    Cons(T, Box<ListStack<T>>),
}

impl<T> ListStack<T> {
    pub fn empty() -> Self { ListStack::Nil }
    pub fn push(self, x: T) -> Self { ListStack::Cons(x, Box::new(self)) }
    pub fn peek(&self) -> Option<&T> {
        match self { ListStack::Cons(x, _) => Some(x), _ => None }
    }
}

Type Signatures

Concept	OCaml	Rust
stack type	`module type STACK with type 'a t`	`struct Stack<T>`
empty stack	`val empty : 'a t` (value)	`fn empty() -> Self` (constructor method)
push	`val push : 'a -> 'a t -> 'a t`	`fn push(self, x: T) -> Self` (consuming)
peek	`val peek : 'a t -> 'a` (raises `Empty`)	`fn peek(&self) -> Result<&T, Empty>`
pop	`val pop : 'a t -> 'a t` (raises `Empty`)	`fn pop(self) -> Result<Self, Empty>`
empty check	`val is_empty : 'a t -> bool`	`fn is_empty(&self) -> bool`

Key Insights

Error handling: OCaml raises Empty as an exception that propagates up the call stack unless caught with try ... with Empty -> .... Rust returns Result<_, Empty>, requiring callers to handle the error case at every call site. The Rust approach makes the failure branch visible in every function signature.

Module signatures vs. types: OCaml uses a module signature (module type STACK) to separate interface from implementation — callers cannot observe that the backing type is a list. Rust achieves the same encapsulation by making items: Vec<T> private — callers can't access the internal Vec directly.

**Consuming self for persistent-style API:** OCaml's push x s returns a new stack value; the original s is still accessible (OCaml lists are persistent). Rust simulates this by consuming self in push(mut self, x: T) -> Self — once pushed, the old binding is moved and only the new stack is accessible. In practice, the inner Vec is mutated in place before being returned, which is an invisible optimization.

Pipeline operator vs. method chaining: OCaml: empty |> push 1 |> push 2 |> push 3. Rust: Stack::empty().push(1).push(2).push(3). Method chaining in Rust reads left-to-right and is syntactically equivalent.

Linked-list alternative: A Box-linked list stack (Cons(T, Box<ListStack<T>>)) is the most direct OCaml analog in Rust, but it allocates one heap node per element. The Vec-backed stack amortizes allocations and is idiomatic for production code.

When to Use Each Style

**Use Vec-backed Stack<T> when:** Building a real stack for production use — amortized O(1) push/pop with contiguous memory is significantly faster than a linked list. **Use ListStack<T> (linked list) when:** Teaching the OCaml parallel explicitly, or when you need true structural sharing between stack versions (e.g., sharing a common suffix between two stacks built from the same base).

Exercises

Implement a truly persistent Stack backed by a singly-linked list using Option<Box<Node<T>>> so that push and pop are O(1) without cloning or mutating a Vec

Add a peek_n(n: usize) -> Result<&T, Empty> method that returns a reference to the nth element from the top without removing anything from the stack

Implement From<Vec<T>> for Stack<T> and From<Stack<T>> for Vec<T> conversion traits, then write a round-trip test that verifies the element order is preserved correctly

Open Source Repos

functional-rust

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

Rust