932 Intermediate

932-stack-module — Stack Module with Signature

Functional Programming

Tutorial

The Problem

Module signatures in OCaml enforce interface contracts: you declare what a module provides (types and functions), and the compiler verifies that implementations satisfy the contract. This enables abstract data types, multiple implementations of the same interface, and documentation by contract. Rust's traits serve the same role: they define a set of methods that concrete types must implement. A Stack trait with push, pop, peek, empty, and is_empty methods can be satisfied by Vec, LinkedList, or a custom persistent stack — all interchangeable behind the trait interface.

🎯 Learning Outcomes

• Define a Stack trait as the Rust equivalent of OCaml's module type STACK

• Implement the trait for a concrete ListStack<T> backed by Vec<T>

• Understand why persistent (functional, non-mutating) stacks require &self returning new values

• Use associated types (type Item) for the element type

• Compare Rust's traits with OCaml's module signatures and include for multiple implementations

Code Example

#![allow(clippy::all)]
/// Stack Module with Signature
///
/// OCaml uses module types (signatures) to enforce abstraction.
/// Rust achieves the same with traits — defining an interface that
/// multiple types can implement.

/// The trait is Rust's equivalent of OCaml's `module type STACK`.
pub trait Stack: Sized {
    type Item;

    fn empty() -> Self;
    fn is_empty(&self) -> bool;
    fn push(&self, item: Self::Item) -> Self;
    fn peek(&self) -> Option<&Self::Item>;
    fn pop(&self) -> Option<Self>;
    fn size(&self) -> usize;
}

/// A persistent (immutable) stack backed by a Vec.
/// Each push/pop returns a new stack — the old one is unchanged.
#[derive(Debug, Clone, PartialEq)]
pub struct ListStack<T> {
    items: Vec<T>,
}

impl<T: Clone> Stack for ListStack<T> {
    type Item = T;

    fn empty() -> Self {
        ListStack { items: Vec::new() }
    }

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

    /// Push returns a new stack with the item on top.
    fn push(&self, item: T) -> Self {
        let mut new_items = self.items.clone();
        new_items.push(item);
        ListStack { items: new_items }
    }

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

    fn pop(&self) -> Option<Self> {
        if self.items.is_empty() {
            None
        } else {
            let mut new_items = self.items.clone();
            new_items.pop();
            Some(ListStack { items: new_items })
        }
    }

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

/// A more efficient mutable stack (idiomatic Rust — ownership-based).
/// This is what you'd actually use in Rust: take ownership, mutate, return.
#[derive(Debug, Clone, PartialEq)]
pub struct MutStack<T> {
    items: Vec<T>,
}

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

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

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

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

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

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

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

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

    #[test]
    fn test_persistent_empty() {
        let s: ListStack<i32> = ListStack::empty();
        assert!(s.is_empty());
        assert_eq!(s.peek(), None);
        assert_eq!(s.pop(), None);
    }

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

    #[test]
    fn test_mut_stack_empty() {
        let mut s = MutStack::<i32>::new();
        assert!(s.is_empty());
        assert_eq!(s.pop(), None);
    }

    #[test]
    fn test_single_element() {
        let s = ListStack::empty().push(42);
        assert_eq!(s.size(), 1);
        assert_eq!(s.peek(), Some(&42));
        let s2 = s.pop().unwrap();
        assert!(s2.is_empty());
    }
}

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
  val pop      : 'a t -> 'a t
  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
  assert (size s = 3);
  assert (peek s = 3);
  let s' = pop s in
  assert (peek s' = 2);
  (* Original unchanged — persistent data structure *)
  assert (peek s = 3);
  print_endline "All assertions passed."

Key Differences

Abstract types: OCaml module signatures can make type t fully abstract (users cannot create values directly); Rust traits cannot hide the implementing type.

Functional vs object: OCaml modules are structural values; Rust traits are interface contracts on objects. Conceptually similar but mechanically different.

Multiple implementations: Rust multiple impl Trait for Type blocks per type; OCaml multiple modules satisfying the same module type.

First-class: OCaml modules are first-class values that can be passed as function arguments; Rust trait objects (dyn Trait) provide similar dynamic dispatch.

OCaml Approach

module type STACK = sig type t; type item; val empty: t; val push: item -> t -> t; val peek: t -> item option; val pop: t -> t option; ... end. A persistent module Stack : STACK with type item = int = struct ... end. OCaml's module system supports first-class modules, functor instantiation, and abstract types opaque to users of the module. Multiple stacks can be created from the same functor MakeStack(T: OrderedType).

Full Source

#![allow(clippy::all)]
/// Stack Module with Signature
///
/// OCaml uses module types (signatures) to enforce abstraction.
/// Rust achieves the same with traits — defining an interface that
/// multiple types can implement.

/// The trait is Rust's equivalent of OCaml's `module type STACK`.
pub trait Stack: Sized {
    type Item;

    fn empty() -> Self;
    fn is_empty(&self) -> bool;
    fn push(&self, item: Self::Item) -> Self;
    fn peek(&self) -> Option<&Self::Item>;
    fn pop(&self) -> Option<Self>;
    fn size(&self) -> usize;
}

/// A persistent (immutable) stack backed by a Vec.
/// Each push/pop returns a new stack — the old one is unchanged.
#[derive(Debug, Clone, PartialEq)]
pub struct ListStack<T> {
    items: Vec<T>,
}

impl<T: Clone> Stack for ListStack<T> {
    type Item = T;

    fn empty() -> Self {
        ListStack { items: Vec::new() }
    }

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

    /// Push returns a new stack with the item on top.
    fn push(&self, item: T) -> Self {
        let mut new_items = self.items.clone();
        new_items.push(item);
        ListStack { items: new_items }
    }

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

    fn pop(&self) -> Option<Self> {
        if self.items.is_empty() {
            None
        } else {
            let mut new_items = self.items.clone();
            new_items.pop();
            Some(ListStack { items: new_items })
        }
    }

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

/// A more efficient mutable stack (idiomatic Rust — ownership-based).
/// This is what you'd actually use in Rust: take ownership, mutate, return.
#[derive(Debug, Clone, PartialEq)]
pub struct MutStack<T> {
    items: Vec<T>,
}

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

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

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

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

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

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

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

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

    #[test]
    fn test_persistent_empty() {
        let s: ListStack<i32> = ListStack::empty();
        assert!(s.is_empty());
        assert_eq!(s.peek(), None);
        assert_eq!(s.pop(), None);
    }

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

    #[test]
    fn test_mut_stack_empty() {
        let mut s = MutStack::<i32>::new();
        assert!(s.is_empty());
        assert_eq!(s.pop(), None);
    }

    #[test]
    fn test_single_element() {
        let s = ListStack::empty().push(42);
        assert_eq!(s.size(), 1);
        assert_eq!(s.peek(), Some(&42));
        let s2 = s.pop().unwrap();
        assert!(s2.is_empty());
    }
}

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
  val pop      : 'a t -> 'a t
  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
  assert (size s = 3);
  assert (peek s = 3);
  let s' = pop s in
  assert (peek s' = 2);
  (* Original unchanged — persistent data structure *)
  assert (peek s = 3);
  print_endline "All assertions passed."

✓ Tests Rust test suite

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

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

    #[test]
    fn test_persistent_empty() {
        let s: ListStack<i32> = ListStack::empty();
        assert!(s.is_empty());
        assert_eq!(s.peek(), None);
        assert_eq!(s.pop(), None);
    }

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

    #[test]
    fn test_mut_stack_empty() {
        let mut s = MutStack::<i32>::new();
        assert!(s.is_empty());
        assert_eq!(s.pop(), None);
    }

    #[test]
    fn test_single_element() {
        let s = ListStack::empty().push(42);
        assert_eq!(s.size(), 1);
        assert_eq!(s.peek(), Some(&42));
        let s2 = s.pop().unwrap();
        assert!(s2.is_empty());
    }
}

Deep Comparison

Stack Module with Signature: OCaml vs Rust

The Core Insight

Both OCaml and Rust enforce abstraction boundaries, but through different mechanisms. OCaml uses module types (signatures) to hide implementation details; Rust uses traits. The interesting tension: OCaml's stack is naturally persistent (immutable), while Rust's ownership model makes mutable stacks more idiomatic.

OCaml Approach

OCaml defines a module type STACK with abstract type 'a t, then implements it as ListStack backed by a plain list. The signature hides the fact that 'a t = 'a list — callers can only use the interface functions. push prepends to the list (O(1)), pop returns the tail — both operations are naturally persistent because lists are immutable. Exceptions (raise Empty) handle error cases, which is the traditional OCaml style before Option/Result became preferred.

Rust Approach

Rust uses a trait Stack with an associated type Item to define the interface. The persistent implementation (ListStack) clones the internal Vec on each operation — more expensive than OCaml's list cons, but maintains immutability. The mutable variant (MutStack) is what idiomatic Rust code would actually use: &mut self methods that modify in place, leveraging ownership to guarantee exclusive access. Rust returns Option instead of raising exceptions.

Side-by-Side

Concept	OCaml	Rust
Interface	`module type STACK`	`trait Stack`
Abstract type	`type 'a t`	`type Item` (associated type)
Error handling	`exception Empty` / `raise`	`Option<T>` / `None`
Persistence	Natural (list = immutable)	Requires cloning Vec
Mutation	Not idiomatic	`&mut self` methods
Encapsulation	Signature hides `'a t = 'a list`	Private fields

What Rust Learners Should Notice

• OCaml's persistent stack is O(1) for push/pop because list cons shares the tail — Rust's Vec-based persistent stack is O(n) due to cloning

• Rust's &mut self mutable stack is the idiomatic choice when you don't need persistence — ownership guarantees no one else holds a reference

• Option<T> in Rust replaces OCaml's exception-based error handling — it forces callers to handle the empty case at compile time

• Traits can have associated types (type Item) which are more flexible than OCaml's abstract types in some ways (they participate in type inference)

• The persistent vs mutable tradeoff is a core design decision in Rust that OCaml programmers rarely face

Exercises

Implement a MutableStack<T> that satisfies a MutStack trait with push(&mut self, item: T) and pop(&mut self) -> Option<T> methods.

Add a map_stack<U> method to the Stack trait that applies a function to all elements and returns a new stack.

Implement Stack for VecDeque<T> and write a use_stack<S: Stack<Item = i32>>(s: S) function that works with any implementation.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Stack Module with Signature: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Side-by-Side

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos