Immutability Matters
Reversing Stacks

It turns out that I omitted the implementation of .Reverse() from my recent post Immutable Stacks Miscellany. Given that a friend has identified an alternative way to implement this, we’ll take a minor detour.

Perhaps the simplest approach (and the one that I had originally) is to create an extension method, based on the IImmutableStack<T> interface to return a new stack:

// Extension methods for working with IImmutableStack<T>
public static class ImmutableStackExtensions
{
    // Create a new stack containing the same items in reverse
    public static IImmutableStack<T> Reverse<T>(
        this IImmutableStack<T> stack)
        where T : IEquatable<T>
    {
        return stack.Aggregate(
            ImmutableStack<T>.Empty,
            (s, i) => s.Push(i));
    }
}

The LINQ .Aggregate() method makes the implementation quite simple. (If you’re not familiar with .Aggregate(), check out this StackOverflow answer for a really good explanation.)

The suggested alternative is to instead extend our existing IImmutableStack<T> interface:

public interface IImmutableStack<T>
{
    // ... elided ...

    // Create a new stack containing the same items in reverse
    IImmutableStack<T> Reverse();
}

Taking this approach requires us to write a separate method for each implementation of the stack, allowing us to optimize for each context.

For an empty stack, reversing the stack is trivially simple, because we just need an empty stack:

internal sealed class EmptyImmutableStack<T>
{
    // ... elided ...

    public IImmutableStack<T> Reverse() => this;
}

For our simple stack, we can also include an optimization to handle the case of a stack with just one item:

public class SimpleImmutableStack<T>
{
    // ... elided ...

    public IImmutableStack<T> Reverse()
    {
        // For a stack of just one item, reuse the existing instance
        if (_rest.IsEmpty)
        {
            return this;
        }

        return this.Aggregate(
            ImmutableStack<T>.Empty,
            (s, i) => s.Push(i));
    }
}

Which approach is better?

On the one hand, we have the .Reverse() extension method that allows us to reverse any implementation of IImmutableStack<T>. This is the exact use case for which extension methods were introduced into C#, allowing implementors to create a rich set of functionality on the base of a simple interface.

However, on the other hand, we only have a couple of implementations of IImmutableStack<T> to worry about, not dozens. Further, writing separate implementations allows us to make some memory saving optimizations with negligable execution cost.

Given that one of the premises of well written immutable data structures is that they make extensive reuse of data wherever possible, I’m leaning towards separate implementations as the preferred approach.