Immutability Matters
Type Miscellany

As we near the end of this series on immutable types (for now, anyway), here’s a grab bag of things that didn’t seem to fit elsewhere.

Naming of helper methods

In the Factory Methods post, we defined the extension method .ToQueue() on IEnumerable<T>, allowing easy creation of a queue from an existing sequence.

To avoid confusion with other queue implementations, one reader suggested this method should be renamed to .ToImmutableQueue() so that readers can’t mistake the kind of queue involved.

I’m of two minds on this. On the one hand, a certain level of explicitness is very helpful when working things for the first time, but after a while, the need to call out things fades away with familiarity.

Consider for example the strong guidance around the async and await keywords which recommended all async methods should end with Async to make their semantics clear. Now that asynchrony has become somewhat mainstream, some practitioners are dropping the suffix in the name of clarity.

Sharing of empty stacks and queues

The example code posted for ImmutableStack<T>.Empty creates a single instance of the empty stack that is then shared. The same approach was used for ImmutableQueue<T>.Empty.

One reader noted that I didn’t really call out these implementations. In both cases, the Empty property was defined as static so that the empty instance was initialized once and then reused.

Given that every single stack needs an empty stack at the end, and that our queue implementations also reference a lot of stacks, the level of reuse is quite high, saving a measurable amount of memory.

Potential for stack overflow in Stack.Equals

The implementation of equality for immutable stacks can throw a stack overflow exception if the stacks being compared are large enough. Interestingly though, I can’t reproduce this on my machine - but a friend of mine can on his. The implementation as shown in the original post uses a form of tail recursion; I therefore suspect that there’s an issue with runtime version, available memory, and possibly other factors.

Fortunately, it’s not hard to rewrite the method using regular iteration:

public bool Equals(IImmutableStack<T> other)
{
    IImmutableStack<T> left = this;
    IImmutableStack<T> right = other;
    do
    {
        if (ReferenceEquals(left, right))
        {
            // Same exact instance, must be equal
            return true;
        }

        if (left.IsEmpty != right.IsEmpty
            || left.GetHashCode() != right.GetHashCode()
            || !Equals(left.Peek, right.Peek))
        {
            // One side is empty and the other is not
            // or they have different hash codes
            // or the top items are different
            return false;
        }

        left = left.Discard();
        right = right.Discard();
    } while (!left.IsEmpty && !right.IsEmpty);

    return left.IsEmpty == right.IsEmpty;
}

What about XML comments?

Including code in a blog entry is a delicate business. On the one hand, it’s often the best way to convey a particular point - especially when the topic at hand is how to write code. But, on the other hand, (almost) no one comes to a blog to read screen after screen of code. Keeping the code examples as minimal as possible makes the blog a bit more accessible.

For code included in this series, I deliberately abbreviated the existing documentation comments, reducing most to simple one-liners and removing some entirely.