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.

Comments

blog comments powered by Disqus
Next Post
Enumeration of Immutable Queues  21 Jan 2017
Prior Post
Simple Immutable Queues  07 Jan 2017
Related Posts
Why Immutable Types?  11 Mar 2017
Immutable Type Miscellany  05 Mar 2017
Testing Immutable Types  25 Feb 2017
Factory Methods  18 Feb 2017
Queue Concatenation  11 Feb 2017
Complex Immutable Queues  04 Feb 2017
The Problem with the Simple Immutable Queue  28 Jan 2017
Enumeration of Immutable Queues  21 Jan 2017
Simple Immutable Queues  07 Jan 2017
Immutable Queues  30 Dec 2016
More immutable-types posts »
Related Pages
January 2017 archive