Saturday 19 November 2016
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