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.

Comments

blog comments powered by Disqus
Next Post
Immutable Stack Diagrams  26 Nov 2016
Prior Post
Method Archetypes  15 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