Immutable collections in C#

This is a follow on from Immutable objects in C# and expands immutability to the level of collections.

Before I start I feel I should point out that collections wrapped by the read only wrapper in C# are NOT immutable, the thing in control of the original collection can change it. Take the following:

var original = new List<int>{1, 1, 2, 3, 5};
var readonly = original.AsReadonly();
readonly.Add(8); // Exception as read only
original.Add(8); 

var last = readonly.Last(); // last = 8

It is clear all AsReadonly() actually does is wrap the original collection in a wrapper that stops manipulation functions being called. If you have access to the original collection reference you can still change it.

This is not immutability... So what is an immutable collection.

Put simply it is a collection that once created is set in stone. If you want to change it you create a copy of the original collection with the changes in place. This sounds costly, and with a naive implementation it can be.

public class ImmutableArray<T> : IEnumerable<T>
{
    private T[] _storage;
    
    public ImmutableArray() 
    {
        _storage = new T[0];
    }
    
    private ImmutableArray(IEnumerable<T> storage) 
    {
        _storage = storage.ToArray();
    }
    
    public int Count => _storage.Length;
    
    public ImmutableArray<T> Add(T item)
        => Add(new[]{item});
    
    public ImmutableArray<T> Add(IEnumerable<T> items)
        => new ImmutableArray(_storage.Concat(items));
        
    // Other operations here
    ...
}

As you can see, this operates a little like the string type. When you make changes it preserves the original values and stores them in a new ImmutableArray that includes the added objects, the original is not touched so anything that has a reference to it is not effected by the change. This is actually not as costly as it might appear for small array sizes.

There are still gotchas in this implementation. If the type T in the array is a mutable object it is still possible that something can mutate values in the mutable objects in the collection, this is the nature of using a hybrid language such as C#.

If you use immutable collection you should only store value types or immutable objects in them or you lose all the benefits, you just incur cost. C# has a great set of Immutable Collections that lifts the collections beyond the naive example above.

So what do they do differently. The key difference will be many of them use balanced binary tree structures or red black trees to store the data. We need to step back a little to see what this buys us.

You should all know what a binary tree is, but here is a quick example:

public class ITreeNode<T>
{
    public T Value { get; }
    
    public ITreeNode<T> Left { get; }
    public ITreeNode<T> Right { get; }
}

So a tree is built of nodes where each node contains a value and might contain nodes to the left or right of the value. You end up with a structure as follows:

    6
   / \
  2   7
   \   \
    4   8
   / \
  3   5

This is where the benefit of immutable collections coupled with immutable objects can be seen, hopefully it should trigger an "ah, I get it" moment.

Say we want to update the object at node 4, we need to do the following.

• Build the updated object at node 4, we can re-use the reference to nodes 3 and 5 because they are immutable so this is safe.
• Build an updated node 2 and connect it to the new node 4
• Build an updated node 6 and connect it to the new node 2

This gives us the following. I have use an "a" suffix to denote the new nodes.

    6a
   / \
  2a  7
   \   \
    4a  8
   / \
  3   5

Anything that holds a reference to the old node 6 root node still has all the data it did before. Anything with the new node 6a root node has the updated structure. Notice how nodes 3, 5, 7 and 8 are shared between the two structures.

So what are the trade offs here because you should be able to see that mutable collections will always carry extra overhead compared to their mutable relations.

The trade off is the absolute safety you get from immutability and the changes in code flow that working with immutable data brings. When you use immutability and pure functions together your code changes. It stops being complex time critical flows that directly manipulate the data you are looking at and working on into discrete steps that take in data do some work and produces a result.

This type of flow then becomes simple processes that are easy to plug together. When debugging you only need to concern yourself with a single process at a time. Does it do what you expect?

There is no way any code that occurred before or after can change the results and that is the huge payoff.

I will see what questions this throws up and decide the direction to take on the next article from there.

Happy coding

Woz