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:

public interface IImmutableStack<T>
{
    /// <summary>
    /// Test to see whether we have an empty stack
    /// </summary>
    bool Empty { get; }

    /// <summary>
    /// Gets the item on the top of the stack
    /// </summary>
    T Peek { get; }

    /// <summary>
    /// Push a new item on the stack, returning the new stack
    /// </summary>
    /// <param name="value">Value to be pushed on the top of the stack.</param>
    /// <returns>New stack with the new value on top.</returns>
    IImmutableStack<T> Push(T value);

    /// <summary>
    /// Discard the top item from the stack, returning a smaller stack.
    /// </summary>
    /// <returns>A smaller stack lacking the top item we've discarded.</returns>
    IImmutableStack<T> Discard();
}

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:

// Internal class because we want to expose the interface instead
internal class SimpleImmutableStack<T> : IImmutableStack<T>
{
    // We don't need a copy of the underlying stack, just a reference
    private readonly IImmutableStack<T> _rest;

    // A simple stack is never empty
    public bool Empty => false;

    public T Peek { get; }

    // To discard our top item, just return our underlying stack
    public IImmutableStack<T> Discard() => _rest;

    // To push an item on top, create a new stack
    public IImmutableStack<T> Push(T value)
    {
        return new SimpleImmutableStack<T>(value, this);
    }
        
    public SimpleImmutableStack(
        T value, IImmutableStack<T> rest)
    {
        Peek = value;
        _rest = rest;
    }
}

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.

// Again, an internal class because we are exposing the interface instead
internal class EmptyImmutableStack<T> : IImmutableStack<T>
{
    // An empty stack is always empty 
    public bool Empty => true;

    // Can never peek an empty stack
    public T Peek => throw new InvalidOperationException();

    // Can't discard the top of an empty stack
    public IImmutableStack<T> Discard()
    {
        throw new InvalidOperationException();
    }

    public IImmutableStack<T> Push(T value)
    {
        return new SimpleImmutableStack<T>(value, this);
    }
}

Lastly, we define a very simple entry point by creating an easy way to access an empty stack.

public static class ImmutableStack<T>
{
    // Initialised once and shared
    public static IImmutableStack<T> Empty
        => new EmptyImmutableStack<T>();
}

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.

Next post in this series:
Stack Diagrams

Comments

blog comments powered by Disqus