When most people first try to implement a "persistent" data structure in Scala, they often confuse immutability with persistence. They think that as long as they wrap their logic in a class, they've achieved the goal. But persistence is specifically about the ability to preserve previous versions of the data structure when it's modified.

The Mutation Leak

I recently looked at some code from a developer who was trying to build a persistent stack for a state-management system. They wrote this:

case class PersistentStack[T](private var elements: List[T] = Nil) {
  def push(item: T): Unit = {
    elements = item :: elements
  }

  def pop(): T = {
    val head = elements.head
    elements = elements.tail
    head
  }

  def top(): T = elements.head
}

// Usage
val stack1 = PersistentStack[Int]()
stack1.push(10)
val stack2 = stack1 // They think they are "versioning" here
stack2.push(20)

println(stack1.top()) // Expected 10, but actually prints 20!

The bug here is the var. The developer thought that by assigning stack2 = stack1, they were capturing a snapshot of the stack at that moment. Instead, they just created two references to the same object. Because push returns Unit and modifies the internal state, stack1 and stack2 are tethered together. If you change one, you change both. This is the exact opposite of persistence.

Returning New States for Structural Sharing

To make this truly persistent, we have to stop thinking about "changing" the stack and start thinking about "evolving" it. In a functional persistent stack, the push and pop operations must return a new instance of the stack.

Here is the corrected approach:

case class PersistentStack[T](elements: List[T] = Nil) {
  def push(item: T): PersistentStack[T] = {
    // We return a new stack instance containing the new list
    this.copy(elements = item :: elements)
  }

  def pop(): (T, PersistentStack[T]) = {
    if (elements.isEmpty) throw new NoSuchElementException("Stack is empty")
    
    // We return both the popped value AND the new version of the stack
    (elements.head, this.copy(elements = elements.tail))
  }

  def top(): T = {
    if (elements.isEmpty) throw new NoSuchElementException("Stack is empty")
    elements.head
  }
}

// Usage now:
val s1 = PersistentStack[Int]()
val s2 = s1.push(10)
val s3 = s2.push(20)

println(s2.top()) // Prints 10
println(s3.top()) // Prints 20

Now, when we call s2.push(20), we aren't touching s2 at all. We are creating s3. The magic here is called structural sharing. Because Scala's List is already immutable, s3 doesn't actually copy the entire list of s2; it just creates a new head node that points to the existing list in s2. This makes the operation $O(1)$ in both time and space.

Handling the Empty State Safely

I'll be honest: throwing NoSuchElementException is lazy. In a professional Scala codebase, you'll almost never see that. Instead, we use Option. If you're building a stack that other developers will use, you should signal that a pop or top might fail if the stack is empty.

By changing the return type of pop to Option[(T, PersistentStack[T])], you force the caller to handle the empty case explicitly. This turns a potential runtime crash into a compile-time requirement to handle the "empty" scenario, which is why we use Scala in the first place.

📋 Practical Task

Implementing a Persistent Undo-Redo History Buffer

In this exercise, you will implement a HistoryBuffer that mimics the "Undo" and "Redo" functionality of a text editor. You must use two persistent stacks to track the state.

Requirements:

• Create a class HistoryBuffer[T] that holds two persistent stacks: undoStack and redoStack.
• Implement a method applyAction(action: T): This should push the new action onto the undoStack and clear the redoStack (since a new action invalidates the redo history).
• Implement a method undo(): This should pop the top element from the undoStack and push it onto the redoStack, returning the new state of the buffer and the action that was undone.
• Implement a method redo(): This should pop the top element from the redoStack and push it back onto the undoStack, returning the new state of the buffer and the action that was redone.
• All methods must be pure; they should return a new instance of HistoryBuffer rather than mutating the existing one.

Hint: Use the PersistentStack logic from the lesson. Your undo and redo methods should return an Option containing a tuple of the action and the new buffer state.