One of the stumbling blocks that gets in the way of people adopting immutable types is a belief that only trivial data structures can be created immutable; that mutability is a prerequisite for doing any real work. It turns out that this isn’t true - in this series of posts, I’ll explore “doing real work” with immutable data structures.
Let’s consider the humble stack - what can we learn from creating an immutable version? We’ll start by declaring an interface:
What should our implementation look like?
Perhaps the key realization is that any non-trivial stack contains two things - the item that’s on top, and a smaller stack beneath. We can use this to create a simple implementation:
This is a bit circular because you have to already have a stack in order to create a new stack. The constructor needs a stack as one of the parameters - how do we get started?
We need to define an empty stack too.
Lastly, we define a very simple entry point by creating an easy way to access an empty stack.
Keeping this static class separate from the implementations is why our first class was named SimpleImmutableStack<T>.
This is a very simple immutable class, but one that provides all the required functionality of a stack. Notice how pushing a new item onto the stack doesn’t involve any copying of data; instead, the new stack just keeps a reference to note that the rest of the stack is “over there”.
Updated 23/1/2017: The implementation for EmptyImmutableStack<T>.Peek now uses an expression bodied declaration.