Example 063: Stack Module with Signature

Difficulty: ⭐⭐ Category: Modules Concept: Defining an abstract data type with a module signature (OCaml) or trait (Rust). The implementation is hidden behind an interface, enforcing encapsulation. Both persistent (immutable) and mutable variants are shown in Rust. OCaml → Rust insight: OCaml's `module type` signatures map to Rust's `trait` definitions — both define an interface that hides implementation details and enables polymorphism.

/// 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."

📊 Detailed 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