063: Stack Module

Difficulty: Intermediate Category: Data Structures Concept: Stack abstraction: push, pop, peek with module/struct encapsulation Key Insight: OCaml uses module signatures to hide implementation; Rust uses struct + impl with private fields.

// 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() }
    }
}

fn main() {
    let mut s = Stack::new();
    s.push(1);
    s.push(2);
    s.push(3);
    println!("peek: {:?}", s.peek());
    println!("pop: {:?}", s.pop());
    println!("peek after pop: {:?}", s.peek());

    let fs = FnStack::empty().push(1).push(2).push(3);
    println!("FnStack peek: {:?}", fs.peek());
}

#[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"

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