Immutability Matters
Stack Diagrams

One reader suggested that the immutable stacks from my previous post would be easier to understand with some accompanying diagrams to illustrate what is going on. Considering the future posts I have in mind for this series, starting with some clear diagrams is a good idea.

Push

Remembering that our implementation from last time makes sure to re-use the existing stack when we push a new item on the top, here’s what happens when we .Push(32) onto an existing ImmutableStack<int>.

We start with a simple immutables stack, containing just one item. When we .Push(32) to add a second item, we get back a fresh reference to a new instance of the stack. This new instance contains our new item for the head of the stack and a reference to the old stack for the remaining items.

Discard

When we have the stack from our previous step and we want to remove the top item by calling `.Discard(), here’s what happens:

Since the larger stack contains a reference to a smaller stack, discarding the top item just involves returning a reference to the smaller stack.