Immutability in C# Part Three: A Covariant Immutable Stack

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?

Comments (24)

  1. Couldn’t we do:

    public interface IStack<+T> {

     … all the stuff you already have…

     IStack<U> Push<U>(U u) where T : U;


    public sealed class Stack<T> : IStack<T>


     … all the stuff you already have…

     public Stack<U> Push<U>(U u) where T : U {

       return new Stack<U>(u, this);



    (notice the sneaky way I just presumed the existence of return-type covariance in this future hypothetical C# version 😉 Of course it works equally well if the method in Stack returns IStack<U> instead)

  2. Gilles Michard says:

    does that mean that sg3.Push(new Tiger("Tony")) would be legal and that the compiler will automatically deduce that the result is of type IStack<Mammal>, finding Mammal from the given Giraffe and Tiger types?

    It would be nice, too.

  3. Eric Lippert says:

    Stuart: you also sneakily added in another feature not currently in C#, namely constraining the type variable U to be a supertype, not a subtype.  

    Yes, if we had return type covariance on virtual overloads/interface implementations AND supertype constraints AND interface variance, then this would all work.  In Scala, which has all those features, you can do exactly that.

  4. Eric Lippert says:

    > the compiler will automatically deduce that the result is of type IStack<Mammal>, finding Mammal from the given Giraffe and Tiger types?

    No, that is not a feature that we want to add to C#. One of the guiding principles of our type inference design is "the type inferrer deduces the best of a set of given types; it never picks a type as "best" which is not in the input set".  

    In this case we would have the set { Giraffe, Tiger } and be unable to pick a best type from that.  That is why in my examples I made sure that the type was either explicitly mammal, or that we were picking from the set {Mammal, Tiger}, which has an unambiguous best type of Mammal.

    Some languages (Java, eg) will attempt to deduce a type not in the input set, but we do not want to go there. It greatly complicates the inference rules, which are already rather complicated.

  5. Jon Skeet says:

    I’m not sure I follow the example, Eric. When you write:


    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.


    Do you mean that it *should* cause an exception, and indeed does, or that due to the immutability (i.e. we’re actually always creating "new" stacks) we’re okay without any exceptions?


  6. Eric Lippert says:

    I mean that in a world where IStack<+T> is legal, the code above would just work as you’d expect and be perfectly typesafe. Because it IS perfectly typesafe.  The only reason that array covariance is broken is because arrays are mutable. Since immutable stacks are immutable, stack covariance is perfectly safe.

  7. Jon Skeet says:

    Good, that’s what I’d hoped 🙂

    The point being that the stack of giraffes is still a stack of giraffes and can never contain anything else because it can never change *at all* – so appearing to add a tiger doesn’t change the view of the world for clients which only have the original stack.

    I think I’m with it now 🙂


  8. Tanveer Badar says:

    It is 1 A.M. and you made me read this post, with sleep gone away. 😉

    I’ll have to dig up my lost C++ skills to see if I can come up with something similar with templates. After all, they are compile-time UTM!

    C++ already has covariant return types for virtual functions, templated conversion operators should take care of supertype conversions and immutables datastructures aren’t any big deal. Only thing missing from the picture is constraints.

  9. WaterBreath says:

    I can mentally extrapolate the workings of immutable versions of most traditional data structures based on what you’ve shown with the stack…  At least all the "linear" ones.  What I’m really curious about is some good ways to create an immutable _tree_.

    It seems like building a useful immutable tree would be a _lot_ more challenging.  For one thing, the structure can diverge at any point, rather than only at the end.  This reveals the limitation of this sort of immutability you have been illustrating: it makes incremental adding and removing very easy, but to insert or remove data at some middle point can be much more complex, and may necessitate breaking the "sharing".

    This type of mid-structure change is such a critical operation for trees that, if it can’t be done without breaking "sharing", then I wonder whether many of the benefits of immutability still apply in most tree use cases.

  10. bleroy says:

    Sweet, but we *want* Push to be on IStack, don’t we?

  11. Timothy Bussman says:

    WaterBreath: There are tons of immutable tree demos on the web.  Google for it and I’m sure you can find a powerpoint or flash animation showing you exactly how it works.

  12. Eric Lippert says:

    I’ll do immutable trees after immutable queues.

  13. Pop Catalin says:

    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"));

    This doesn’t work !!! Because :

    IStack<Mammal> sm4 = sm3.Push(new Tiger("Tony")) is actually

    IStack<Mammal> sm4 = sm3.Push<Tiger>(new Tiger("Tony"))

    because the type is inferred from from type of the parameter that the method is called with

    but inside the constructor you’ll have

    private Stack(T head, IStack<T> tail)


               this.head = head;

               this.tail = tail;



    private Stack(Tiger head, IStack<Tiger> tail)


               this.head = head;

               this.tail = tail;


    abd you call the constructor with this call

    Stacknew Tiger(("Tony"), sm3) … sm3 is sg3 witch is an IStack<Giraffe> so you bassically pass to to a constructor taking a tiger and a IStack<Tiger> and IStack<Giraffe> … wich violates type safety.

  14. Pop Catalin says:

    it’s 4:30 AM where I live but this ideea just pierced through my brain, because I can’t sleep

    This is how you can have covariance in .Net

    let’s say you want a method that pushes an animal in a queue and pops another one from the same queue


    public Animal Foo<Animal+>(Queue<Animal> queue) {

      Animal an = new Animal();


      return queue.Pop();


    what can you do to make the method work by passing an Queue<Giraffe>? this is the ideea

    the method above should exactly equivalent with :


    public Animal Foo<T>(Queue<T> queue) where T: Animal, new() {

      T an = new T();


      return queue.Pop();


    so now the first method can be called with an Queue<Giraffe>

    Foo<Animal+>( new Queue<Giraffe)  // works because Animal+ is a T generic parameter that is of Animal type.

    Also this means if you write Bar<SomeType+> you don’t create a closed generic definition but an open one and the instantiation is only when the method is called with a certain type.

    Also you need to allow references to open generic types, for example

    Queue<Animal+> q = new Queue<Giraffe>();

    this is a reference to Queue<T> where T: Animal like so (a reference to an open generic type)

    Queue<T> where T: Animal q = new Queue<Giraffe>(); //  ****** just like an object reference can point to any type instance and reference to an open generic type should be able  to point to any type constructed from  it ******

    so now

    when the method Foo<Animal+>(…) is called

    var x = Foo( new Queue<Tigger>()); //x is inferred as Animal

    The whole point is:

    –  with those 2 things :

    * allowing references to open generic types to be assigned with constructed types

    Another ex:

    List<Animal+> l1, l2; List<Animal+> is List<T> where T: Animal

    l1 = new List<Giraffe>;

    l2 = new List<Monkey>

    * Covariant and contravariant parameters should create open generic types not closed ones.

    is all that is needed to have covariance in .Net


    public Animal+ Foo<Animal+> (Queue<Animal> queue) should be

    equivalent with :

    public T Foo<T>(Queue<T> queue) where T: Animal

    P.S. doing this mental exercise i’ve found that .Net already has half the necesary things for covariance to work (  open generic methods already are covariant or contravariant…I hate those terms really)

  15. Eric Lippert says:

    > IStack<Mammal> sm4 = sm3.Push(new Tiger("Tony")) is actually

    > IStack<Mammal> sm4 = sm3.Push<Tiger>(new Tiger("Tony"))

    > because the type is inferred from from type of the parameter that the method is called with

    Nope.  Did you actually try it? (Obviously the covariant conversion will not work, but this call will.)

    Hint: the type argument for the generic method is inferred from more than just the "new Tiger" parameter.

  16. Gilles Michard says:

    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#?

  17. David says:

    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?

  18. Eric Lippert says:

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

  19. David says:

    So you did 🙂 Looks like I have a lot more reading to do.

  20. cipto says:

    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.

  21. Eric Lippert says:

    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.

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

  23. Rob Paveza says:

    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. 🙂

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

Skip to main content