Immutability Matters
Stack Equality

As previously discussed, it is important to implement an appropriate definition of Equality for most .NET classes. Let’s extend our immutable stack implementation appropriately.

I suggest that value semantics are appropriate for stacks - that one stack containing [1, 2, 3] and another stack containing [1, 2, 3] should be considered as equal, because there’s no way to tell them apart should one be swapped for another.

We begin by modifying our interface declaration to include IEquatable<T>; this provides a better API for our consumers than just overriding Equals(object).

public interface IImmutableStack<T> : IEquatable<IImmutableStack<T>>
    where T : IEquatable<T>
{
    // ... elided ...
}

As we want to compare two stacks to see if they are equal, we need the items in our stacks to be comparable as well, so we include the constraint on T.

The implementation for EmptyImmutableStack<T> is very easy, as every instance can be substituted for any other, so we only need the check for null and a check for the type.

// Implement IEquatable<IImmutableStack<T>>
public bool Equals(IImmutableStack<T> other) 
    => other?.GetType() == GetType();

public override bool Equals(object obj) 
    => Equals(obj as ImmutableStack<T>);

// Delegate to the hashcode of the type
public override int GetHashCode() 
    => GetType().GetHashCode();

Performance is something to consider when we implement for SimpleImmutableStack<T>, as we don’t want to be comparing every item in the stack if we don’t have to.

Remember that implementing equality involves overriding Equals(object), and that requires also overriding GetHashCode(). The contract between these methods is simple - equal objects must have equal hash codes, and the hash code must never change during the lifetime of the object.

We can use this contract to make our code more efficient - we’ll cache the value of GetHashCode() to avoid recalculation every time we use it, and we’ll use it to short-circuit our Equal(IImmutableStack<T>) implementation.

// We cache our hashcode to avoid recalculation
private readonly int _hashCode;

public SimpleImmutableStack(T value, IImmutableStack<T> rest)
{
    Peek = value;
    _rest = rest;

    // Precalculate our hash code up front
    var valueHash = value?.GetHashCode();
    _hashCode = _rest.GetHashCode() * 17 ^ (valueHash ?? 0);
}

public override int GetHashCode() => _hashCode;

public override bool Equals(object obj)
    => Equals(obj as ImmutableStack<T>);

public bool Equals(IImmutableStack<T> other)
{
    if (other == null
        || other.Empty
        || other.GetHashCode() != _hashCode)
    {
        return false;
    }

    if (ReferenceEquals(this, other))
    {
        return true;
    }

    if (!Peek.Equals(other.Peek))
    {
        return false;
    }

    return _rest.Equals(other.Discard());
}

How does this work?

• If other is null or an empty queue, we’re obviously not equal.
• If the hash codes are different, we’re not equal.
• If both this and other are the same exact instance, we’re equal.
• If the items on the top of the stack not equal, we’re not equal.
• Otherwise, check the remainder of the stack for equality.