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.


blog comments powered by Disqus
Next Post
Enumerating Immutable Stacks  03 Dec 2016
Prior Post
Immutable Stacks  19 Nov 2016
Related Posts
Why Immutable Types?  11 Mar 2017
Immutable Type Miscellany  05 Mar 2017
Testing Immutable Types  25 Feb 2017
Factory Methods  18 Feb 2017
Queue Concatenation  11 Feb 2017
Complex Immutable Queues  04 Feb 2017
The Problem with the Simple Immutable Queue  28 Jan 2017
Enumeration of Immutable Queues  21 Jan 2017
Reversing Immutable Stacks  14 Jan 2017
Simple Immutable Queues  07 Jan 2017
More immutable-types posts »
Related Pages
November 2016 archive