Immutability in C# Part Two: A Simple Immutable Stack

Immutability in C# Part Two: A Simple Immutable Stack

Rate This
  • Comments 61

Let’s start with something simple: an immutable stack.

Now, immediately I hear the objection: a stack is by its very nature something that changes. A stack is an abstract data type with the interface

void Push(T t);
T Pop();
bool IsEmpty { get; }

You push stuff onto it, you pop stuff off of it, it changes. How can it be immutable?

Every time you need to make a data structure immutable, you use basically the same trick: an operation which “changes” the data structure does so by constructing a new data structure. The original data structure stays the same.

How can that possibly be efficient? Surely we’ll be allocating memory all over the place! Well, actually, in this case, no. An immutable stack is every bit as efficient as a mutable stack. Even better: in some cases, it can be considerably more efficient, as we'll see.

Let’s start by defining an interface for our immutable structure. While we’re at it, we’ll fix a problem with the stack ADT above, namely that you cannot interrogate the stack without changing it. And we’ll make the stack enumerable just for the heck of it:

    public interface IStack<T> : IEnumerable<T>
    {
        IStack<T> Push(T value);
        IStack<T> Pop();
        T Peek();
        bool IsEmpty { get; }
    }

Pushing and popping give you back an entirely new stack, and Peek lets you look at the top of the stack without popping it.

Now let’s think about constructing one of these things here. Clearly if we have an existing stack we can construct a new one by pushing or popping it. But we have to start somewhere. Since every empty stack is the same, it seems sensible to have a singleton empty stack.

    public sealed class Stack<T> : IStack<T>
    {
        private sealed class EmptyStack : IStack<T>
        {
            public bool IsEmpty { get { return true; } }
            public T Peek() { throw new Exception("Empty stack"); }
            public IStack<T> Push(T value) { return new Stack<T>(value, this); }
            public IStack<T> Pop() { throw new Exception("Empty stack"); }
            public IEnumerator<T> GetEnumerator() { yield break; }
            IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
        }
        private static readonly EmptyStack empty = new EmptyStack();
        public static IStack<T> Empty { get { return empty; } }
        private readonly T head;
        private readonly IStack<T> tail;
        private Stack(T head, IStack<T> tail)
        {
            this.head = head;
            this.tail = tail;
        }
        public bool IsEmpty { get { return false; } }
        public T Peek() { return head; }
        public IStack<T> Pop() { return tail; }
        public IStack<T> Push(T value) { return new Stack<T>(value, this); }
        public IEnumerator<T> GetEnumerator()
        {
            for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop())
                yield return stack.Peek();
        }
        IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();}
    }

And now we can easily create stacks and push stuff onto them. Notice how the fact that we have immutability means that stacks with the same tail can share state, saving on memory:

IStack<int> s1 = Stack<int>.Empty;
IStack<int> s2 = s1.Push(10);
IStack<int> s3 = s2.Push(20);
IStack<int> s4 = s2.Push(30); // shares its tail with s3.

Painless. Next time: a variant variation on this theme.

  • Of course there are no silver bullets in multithreaded programming. That is a corrollary of the fact that there are no silver bullets in ANY kind of programming. A point that I return to over and over again in this blog is that good design and engineering is a process of making and identifying tradeoffs.

    My point in this series is merely to point out that designing, implementing and using immutable data structures gives you yet another tool in your toolbox which you can consider when faced with a tough problem, particularly a problem involving multithreading. Whether it is the right tool or not depends upon the task at hand.

  • For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

  • Eric,

    Excellent.. then you and I are in agreement, since there are most definitely uses for immutability in the toolbox... as long as they are intelligently applied.

  • I have to agree with Kaveh Shahbazian on this one: fun cannot be null. :)

    My question is why change a way of programming in order to teach people immutability when you can change the compiler to take care of things like that in care of concurency and multi-processor computing? I think the whole FP and immutability buzz is generated by people thinking to abstractly to be able to debug anything :)

  • Previously we discussed a multi-thread safe queue like data structure using locks as an internal synchronization

  • Previously we discussed a multi-thread safe queue like data structure using locks as an internal synchronization

  • Functional programming is in. There is a lot of buzz around the future of functional programming as applications

  • This is genius...

    I'm using this algorithm to store the numbers 1-40 in a immutable stack:

    IStack<int> s0 = Stack<int>.Empty;

    IStack<int> s1 = s0.Push(1);

    IStack<int> s2 = s1.Push(2);

    IStack<int> s3 = s2.Push(3);

    IStack<int> s4 = s3.Push(4);

    IStack<int> s5 = s4.Push(5);

    IStack<int> s6 = s5.Push(6);

    IStack<int> s7 = s6.Push(7);

    IStack<int> s8 = s7.Push(8);

    IStack<int> s9 = s8.Push(9);

    IStack<int> s10 = s9.Push(10);

    IStack<int> s11 = s10.Push(11);

    IStack<int> s12 = s11.Push(12);

    IStack<int> s13 = s12.Push(13);

    IStack<int> s14 = s13.Push(14);

    IStack<int> s15 = s14.Push(15);

    IStack<int> s16 = s15.Push(16);

    IStack<int> s17 = s16.Push(17);

    IStack<int> s18 = s17.Push(18);

    IStack<int> s19 = s18.Push(19);

    IStack<int> s20 = s19.Push(20);

    IStack<int> s21 = s20.Push(21);

    IStack<int> s22 = s21.Push(22);

    IStack<int> s23 = s22.Push(23);

    IStack<int> s24 = s23.Push(24);

    IStack<int> s25 = s24.Push(25);

    IStack<int> s26 = s25.Push(26);

    IStack<int> s27 = s26.Push(27);

    IStack<int> s28 = s27.Push(28);

    IStack<int> s29 = s28.Push(29);

    IStack<int> s30 = s29.Push(30);

    IStack<int> s31 = s30.Push(31);

    IStack<int> s32 = s31.Push(32);

    IStack<int> s33 = s32.Push(33);

    IStack<int> s34 = s33.Push(34);

    IStack<int> s35 = s34.Push(35);

    IStack<int> s36 = s35.Push(36);

    IStack<int> s37 = s36.Push(37);

    IStack<int> s38 = s37.Push(38);

    IStack<int> s39 = s38.Push(39);

    IStack<int> s40 = s39.Push(40);

    programming was never easier before, but the best is, it's threadsafe ;) no one will ever change the stuff i stored in the stack.

    thank you Eric, made my day...

  • I'm coming to this really late, and I'm probably failing to see the joke, so this is a waste of time, but I can't resist informing Gustav that he could have written:

    Enumerable.Range(1, 40).Aggregate(Stack<int>.Empty, (s, n) => s.Push(n));

  • In this post I'll delve into the functional programming techniques that were used to develop ImplicitStyleManager

  • IStack<int> s1 = Stack<int>.Empty;

    IStack<int> s2 = s1.Push(10);

    s2 = s2.Push(15);  //??

    would it possible or should the above statement exists in immutable world?

    I tried to run the statement, and it appear that the s2 now has head with value 15, and it's tail have a IStack which the head value is 10. Kinda strange to me as I still new to this world.

    It is consider that the s2 been mutated?

  • Here is a link talk about the rules for immutable type:

    http://www.bluebytesoftware.com/blog/2007/11/11/ImmutableTypesForC.aspx

    Rules number five:

    5. Immutable types must not leak the ‘this’ reference during construction.

           public IStack<T> Push(T value) { return new Stack<T>(value, this); }

    Wonder if the above statement break the rules?

  • I talked a little bit about patterns using InvocationExpression in a previous post (you might want to

  • I talked a little bit about patterns using InvocationExpression in a previous post (you might want to

  • I think in the future there should be some kind of standard (maybe possible in naming conventions only) regarding methods on immutable vs mutable objects. How often did we do

    myString.Replace("monster", "zombie")

    and forgoet to reassign the result to myString. That method name is clearly a design mistake. If the method was called

    myString = myString.GetReplaced("monster", "zombie")

    or, because of the chainable nature

    myString = myString.WithReplaced("monster", "zombie").WithReplaced("chainsaw", "pump gun")

    things would be so much clearer.

    The same would go for immutable collections. How many would fail in the beginning that myCollection.Add(...) actually doesn't do anything but returns a new object. So immutable collections should as well have an API with method names that communicate that the inner state is not modified but rather a new instance is returned, e.g.

    myFavoriteMovies = myFavoriteMovies.WithAdded("Night of the Living Dead").WithAdded("Friday the 13th").WithRemoved("Titanic");

Page 4 of 5 (61 items) 12345