1002 Intermediate

Stack Module with Signature

Functional Programming

Tutorial

The Problem

Implement a persistent functional stack: a data structure where push and pop return new stacks rather than mutating in place. Model the OCaml module signature pattern in Rust's type system.

🎯 Learning Outcomes

• How OCaml module signatures map to Rust trait bounds and struct APIs

• Implement a persistent interface using consuming methods (self by value) so each operation returns a new stack

• Use Result to handle the empty-stack error case that OCaml raises as an exception

Code Example

#![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')

Key Differences

Error handling: OCaml raises the Empty exception on peek/pop; Rust returns Result<_, Empty>, making the error case explicit in the type

Persistence mechanism: OCaml's list prepend is O(1) and naturally persistent; Rust's Vec-backed implementation clones on each push/pop call for logical persistence

Module vs. type: OCaml uses a module signature to define the stack interface; Rust encodes the same contract as inherent methods on a concrete struct

OCaml Approach

OCaml defines a STACK module signature and implements it with ListStack, backed by a list. push is x :: s (prepend), pop returns the tail, peek returns the head. Errors raise the Empty exception rather than returning an option type.

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));
    }
}

Exercises

Implement a Stack backed by a singly-linked list using Option<Box<Node<T>>> instead of Vec<T> for O(1) push and pop without cloning

Add a peek_n(n) method that returns a reference to the nth element from the top without removing anything

Implement From<Vec<T>> for Stack<T> and From<Stack<T>> for Vec<T> to make the stack interoperable with standard collections

Open Source Repos

functional-rust

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

Rust