Immutability in C# Part 4: True Collection Immutability

In the last article, we looked at how to make types that contained collections immutable. We did this by making the collection readonly, and by storing immutable objects in the collection.

In this article, we’ll implement an example of a truly immutable collection type that we can populate and change. The solution will also be pragmatic. We’re not going to build a production-standard class which deals with all corner-cases, and we’re not going to include unit tests. Really we’re just interested in the implementation details.

Naturally, when we want to modify the contents of this collection we’ll have to emit a new collection instance with the changed contents (preserving the original, and thus retaining mutability).

This sounds expensive, but it needn’t be, and we’ll see that it actually leads to an implementation that is more elegant and simple than its mutable counterpart.

The collection that we’re going to implement is an Immutable Generic Stack. So, let’s define our class:

class ImmutableStack<T> { }

A Stack is a data structure that operates on a Last-In, First-Out basis. We push an item onto the top of a stack, and it is the first item to be popped off (unless, of course you push another item on top of that).

The key our stack implementation is how to represent its contents conceptually. We might imagine some sort of array that we expand or shrink as we add or remove items, but then we have the consideration of how we copy around or modify that array.

In fact, the simplest way to visualise a stack is as a structure that has just two fields:

  • A head: a single item of type T
  • A tail: another ImmutableStack<T>

So, let’s add them into our class:

class ImmutableStack<T>
{
    private T head = default(T);
    private ImmutableStack<T> tail = null;
}

To implement our stack, we need the following features

  • .Push() method to add an item onto the top of the stack
  • .Pop() method to remove the top item from the stack
  • .Peek() method to look at the top item
  • Enumeration over the stack contents

When we Push an item onto a stack we return a new instance with the head as our new item, and the tail as the current stack instance. To implement this, we’ll need a two-parameter constructor and a push function like so:

public ImmutableStack(T head, ImmutableStack tail)
{
    this.head = head;
    this.tail = tail;
}

public ImmutableStack Push(T newItem)
{
    return new ImmutableStack(newItem, this);
}

When we Pop an item off from our stack we simply return the tail. This function will suffice:

public ImmutableStack<T> Pop()
{
    return this.tail;
}

Note with both the Push and Pop we return a different (and sometimes new) instance of the immutable stack. There is nothing about any stack that we change, we merely create new or return existing.

If we want to Peek at an item we return the head. Quite simply:

public T Peek()
{
    return head;
}

To enumerate, we iteratively Peek, Pop, Peek, Pop until we are done. Firstly, however, we must make our class enumerable:

class ImmutableStack<T> : IEnumerable<T>
{
    // Other code

    public IEnumerator<T> GetEnumerator()
    {
        // implementation
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

We’re almost at a stage where we can iterate over an instance of this class. We just need to provide an implementation for IEnumerable.GetEnumerator():

public IEnumerator<T> GetEnumerator()
{
    var current = this;

    while (current.Pop() != null)
    {
        yield return current.Peek();
        current = current.Pop();
    }
}

One final thing we need to do to make this class usable is to clear up a small but important corner-case, the root stack item. We need for this to be an empty stack. which is achievable currently, but is a requirement of the class client.

All that is required is a default constructor. And, adding this in means that we can protect the existing constructor:

public ImmutableStack() {}

private ImmutableStack(T head, ImmutableStack<T> tail)
{
    this.head = head;
    this.tail = tail;
}

Now, to create a new immutable stack, all a client needs to do is:

var stack = new ImmutableStack();

For completeness, here is the full class implementation:

class ImmutableStack : IEnumerable
{
    private T head = default(T);
    private ImmutableStack tail = null;

    public ImmutableStack() { }

    private ImmutableStack(T head, ImmutableStack tail)
    {
        this.head = head;
        this.tail = tail;
    }

    public ImmutableStack Push(T newItem)
    {
        return new ImmutableStack(newItem, this);
    }

    public ImmutableStack Pop()
    {
        return this.tail;
    }

    public T Peek()
    {
        return head;
    }

    public IEnumerator GetEnumerator()
    {
        var current = this;

        while (current.Pop() != null)
        {
            yield return current.Peek();
            current = current.Pop();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Personally, I find the above solution to be very elegant, simple and efficient.

Here is some test code that I ran against the class:

var stack = new ImmutableStack();
stack = stack.Push(0);
stack = stack.Push(1);
stack = stack.Push(2);
stack = stack.Push(3);
stack = stack.Push(4).Push(20);
stack = stack.Push(5);

foreach (int i in stack)
{
    Console.WriteLine(i);
}

Console.WriteLine();

stack = stack.Pop();
stack = stack.Pop();
stack = stack.Push(7);
foreach (int i in stack)
{
    Console.WriteLine(i);
}

Of worthy note is Line 6 where demonstrate that the class supports chaining of operations.

And here are the results when run in a console app.

MutableStackResults

Now we’ve got the end of this, I can confess something that I’ve known all along: Implementing your own mutable stack is futile! Or, at least, it will be on the advent of .NET 4.5.1.

More on this next time in Ready-Made Immutability.

Leave a Reply