Immutability in C# Part Three: A Covariant Immutable Stack

Immutability in C# Part Three: A Covariant Immutable Stack

Rate This
  • Comments 24

Now suppose we had a hypothetical future version of C# in which interface covariance worked, and we wanted a covariant immutable stack. That is, we want to be able to implicitly convert an IStack<Giraffe> to IStack<Mammal>. As we've already discussed, this doesn't make much sense in an array, even though doing so is legal in C# today. If you cast a Giraffe[] to Mammal[] then you can try to put a Tiger into the Mammal[] and it will fail at run time. It seems like the same should be true of stacks -- if you cast an IStack<Giraffe> to IStack<Mammal> then you can push a Tiger onto the stack of Giraffes, which should fail, right?

Maybe. Maybe not.

The interface we defined the other day is not suitable for covariance because it uses the variant parameter as both an input and and output. Let's get a bit crazy for a minute here -- suppose we got rid of the input on the Push:

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

This interface is now suitable for covariance. If you have a stack of Giraffes and you want to treat it as a stack of Mammals, you can do so with perfect type safety, since we know that we will never be pushing a Tiger onto that thing. We'll only be reading off Giraffes, all of which are Mammals. This may seem less than useful, but we'll see what we can do:

    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> 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 static IStack<T> Push(T head, IStack<T> tail) { return new Stack<T>(head, tail); }
        public IEnumerator<T> GetEnumerator()
        {
            for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop())
                yield return stack.Peek();
        }
        IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();}
    }

Notice that Push has disappeared from the empty stack and is static on the nonempty stack, and hey, check it out:

IStack<Giraffe> s1 = Stack<Giraffe>.Empty;
IStack<Giraffe> s2 = Stack<Giraffe>.Push(new Giraffe("Gerry"), s1);
IStack<Giraffe> s3 = Stack<Giraffe>.Push(new Giraffe("Geoffrey"), s2);
IStack<Mammal> s4 = Stack<Mammal>.Push(new Tiger("Tony"), s3);

Oh my goodness, we just pushed a Tiger onto a stack of Mammals that is actually a stack of Giraffes underneath, but everything is still typesafe! There is nothing we can do here to cause an exception at runtime in the type system. It all just works. All the stacks of Giraffes continue to be stacks of Giraffes; they're immutable, so they could hardly be anything else.

This code is pretty ugly though. So...

    public static class Extensions
    {
      public static IStack<T> Push<T>(this IStack<T> s, T t)
      {
        return Stack<T>.Push(t, s);
      }
    }

and now we can say

IStack<Giraffe> sg1 = Stack<Giraffe>.Empty;
IStack<Giraffe> sg2 = s1.Push(new Giraffe("Gerry"));
IStack<Giraffe> sg3 = s2.Push(new Giraffe("Geoffrey"));
IStack<Mammal> sm3 = sg3; // Legal because of covariance.
IStack<Mammal> sm4 = sm3.Push(new Tiger("Tony"));

Is that slick or what?

Next time: what about an immutable queue?

  • Is there a hope that anonymous types { Ta a, Tb b} would implement the covariant interface

    interface IAnonymous_a_b<+Ta,+Tb>{

    Ta a { get;}

    Tb b { get;}

    }

    Combined with an automatic type inference (most derived compatible type) , it would really help with Enumerable.Concat when using different types (casting to an anonymous type is not possible)

    Perhaps VB will do that if not C#?

  • Will the hypothetical covariant C# have a way of enforcing covariantability (is that a word)? For example, would it be possible to add a "covariant" keyword to a type definition, and then have the compiler enforce that all operations in that type are covariant?

  • Yes. I just wrote a ten part series of blog posts on exactly that subject.

  • So you did :) Looks like I have a lot more reading to do.

  • Hi, em i try ur code

    Where to put this code below,so the code can work:

    public static class Extensions

       {

         public static IStack<T> Push<T>(this IStack<T> s, T t)

         {

           return Stack<T>.Push(t, s);

         }

       }

    IStack<+T> , + is unexpected token

    how come + generate error

    is this for .net 2.0 or not?

    Please give me a complete listing code, so i can follow this one,

    i've followed your part one and two and success.

  • The point of this was that IF we add covariance to the language in some future version, THEN this would work. We have not yet added covariance, so this does not work.

    See my recent ten part series on covariance for more details.

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

  • Hi Eric,

    I've just read through pretty much your entire series on covariance and contravariance.  I'd certainly love to see support for it (and it may start making its way into my blog series on my C# wishlist), but I have to say: I don't like the example in this blog post.

    Above all, I don't like that we've created a new imaginary interface IStack<+T> that has every operation for a stack *except* for Push().  A Stack is a well-known and well-understood data structure - they even talked about it at university! - and to create an interface, which models behavior, but to not include all of the behavior for the explicit purpose of supporting a language feature seems wrong.  It feels like coincidental cohesion.

    I also have a substantial problem with the use of an extension method to implement Push().  I've mentioned this in at least two talks I've presented on C# 3.0 and extension methods, not to mention my blog: Extension methods allow developers to feel like they have a twisted kind of multiple inheritance, except that it's not MI at all because there's no virtual method.  The compiler, and consequently the runtime, binds to the extension method unless it can explicitly resolve the method on the defining class or interface, but even if the real implementation class was Stack<T> which implements Push(), but the variable is declared as IStack<+T>, we'll use the extension method.  This is a scary thought when you consider applying this solution to non-data-structure classes with virtual methods that are no longer making virtual calls.

    Now, to qualify: I've never said that extension methods are bad; I've simply said that software developers need to be cognizant of the fact that they might not always be calling what they think they're calling.  IntelliSense and the compiler make it feel like we're operating on a real behavior of objects.

    FWIW, I saw someone else post syntax such as:

    delegate U Action<* is T, U is *<(T item);

    I think that's fantastic syntax. :)

  • So nicely step by step blogged by Eric Lippert for &quot;Covariance and Contravariance&quot; as &quot;Fabulous

Page 2 of 2 (24 items) 12