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.

  • PingBack from http://msdnrss.thecoderblogs.com/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack/

  • Correct me if I'm wrong, but with this approach if I wanted to get the traditional behavior of Stack.Pop I would need to perform a Stack.Peek before Stack.Pop as the value (i.e. "head") is not part of the Stack returned by Stack.Pop. I find this odd, but maybe only due to how I've been programmed to think about a Stack.

  • TSHAK:

    That's true, but I can't imagine it could reasonably work any other way and still preserve immutability.

  • Any why is it the case that _looking_ at a data structure should _require_ you to change its contents? That has never made any sense to me.  

  • That's the same behavior as the STL's stack class. Seems reasonable (and not at all unusual) to me.

  • Cool stuff.

    I'd make one change, from:

           private static readonly EmptyStack empty = new EmptyStack();

           public static IStack<T> Empty { get { return empty; } }

    to:

           public static IStack<T> Empty = new EmptyStack();

    As per:

           http://blogs.msdn.com/jaybaz_ms/archive/2004/04/29/123333.aspx

    Keep up the immutable fight! (whatever that means)

  • I wrote something like a Monad (which I have named it Monad!) in C# 3. I can achieve immutability throe it to an acceptable degree.  Still I am meditating on it. But it looks somehow interesting to me. Here is the code:

    public class Monad&lt;T&gt; : IMonad&lt;T&gt;

    {

       private Monad (T inner) { this.__InnerHolder = inner; }

       private Monad () { }

       private readonly T __InnerHolder;

       private T Inner { get { return __InnerHolder; } }

       public static IMonad&lt;TInner&gt; Unit&lt;TInner&gt; (TInner inner) { return new Monad&lt;TInner&gt; (inner); }

       public static Func&lt;A, IMonad&lt;R&gt;&gt; Lift&lt;A, R&gt; (Func&lt;A, R&gt; fun)

       {

           if (fun.IsNull ()) throw new ArgumentNullException ("fun", "'fun' can not be null.");

           return (a =&gt; Unit&lt;R&gt; (fun (a)));

       }

       public static IMonad&lt;B&gt; Bind&lt;A, B&gt; (IMonad&lt;A&gt; a, Func&lt;A, IMonad&lt;B&gt;&gt; fun)

       {

           if (fun.IsNull ()) throw new ArgumentNullException ("fun", "'fun' can not be null.");

           return new Monad&lt;B&gt; (fun (a.Monad.Inner).Monad.Inner);

       }

       #region IMonad&lt;T&gt; Members

       Monad&lt;T&gt; IMonad&lt;T&gt;.Monad

       {

           get { return this; }

       }

       #endregion

    }

    public static partial class MonadExtra

    {

       public static IMonad&lt;TInner&gt; Unit&lt;TInner&gt; (this TInner inner) { return Monad&lt;object&gt;.Unit&lt;TInner&gt; (inner); }

       public static Func&lt;A, IMonad&lt;R&gt;&gt; Lift&lt;A, R&gt; (this Func&lt;A, R&gt; fun)

       {

           return Monad&lt;object&gt;.Lift&lt;A, R&gt; (fun);

       }

       public static IMonad&lt;B&gt; Bind&lt;A, B&gt; (this IMonad&lt;A&gt; a, Func&lt;A, IMonad&lt;B&gt;&gt; fun)

       {

           return Monad&lt;object&gt;.Bind&lt;A, B&gt; (a, fun);

       }

    }

    public interface IMonad&lt;T&gt;

    {

       Monad&lt;T&gt; Monad { get; }

    }

  • Quite fine. You can think of C# 3.0 query expressions as using a form of monads. I might do a series of blog articles about that at some point.

  • Why doesn't Pop use a ref variable to return the value?

  • Sorry for scrambled code! I have replaced < and > with html literals. It seems that i was wrong about them!

  • For the third time: why should it be necessary to _change_ the data structure in order to _look_ at it? A Pop which returns the value is a design flaw; it conflates two logically distinct and separate operations into one method.

  • this is fine enough i suppose, but it seems that it just pushes management to someone else.

    i.e. you, the caller, now have to constantly pass the stack around, instead of having it as a member variable or similar.

    i mean it's immutable, fine. but so what? now life is harder when we use it. it kind of seems like this sort of strategy would be more error prone; pushing more work back onto the caller.

  • Silky,  This only part 2.  You have to be patient and wait for the Journey to unfold.

  • @Jay:

    public static readonly IStack<T> Empty = new EmptyStack();

  • I don't understand; why can you not have an immutable stack as a member variable? (In a couple posts I'll be having data structures with immutable stacks as member variables.)

    Integers are also immutable. What are the disadvantages of immutable stacks which are shared by immutable integers? How do immutable integers "push work back onto the caller"?

Page 1 of 5 (61 items) 12345