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.


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.


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.

Prior post in this series:
Next post in this series:
Enumerating Stacks


blog comments powered by Disqus