Nerding out about covariance and immutability

I've been working with C# most of my career, but every so often they add bits to the language which for some reason I've never really got to make use of. And "covariance" is one of those things. But I picked up a beta copy of a great new book recently (Eric Lippert's "Fabulous Adventures in Data Structures and Algorithms" from Manning) and it had a simple but fascinating example of a situation where this can work. It taught me something that maybe you might find interesting too...

Hang on, what is covariance? url copied!

As programmers in Object Oriented languages we're used to the idea that a derived type can be cast back to it's parent. So for example if you have a base class for Vehicle and you create concrete classes from that for Car and Bike:

abstract class Vehicle { }
class Car : Vehicle {}
class Bike : Vehicle {}

					

Then if you have an instance of Car it can always be assigned to a variable of type of Vehicle:

Car car = new();
Vehicle vehicle = car;

					

But what happens if you have one of .Net's standard collection types instead of a single instance? Well in this scenario it's a tad more complicated, but being able to cast a collection like that is called covariance. C# does allow it, but only in very specific circumstances.

If you write the same sort of expression with collections it won't work:

List<Car> cars = [new Car(), new Car(), new Car()];
List<Vehicle> vehicles = cars;

					

This gets you a Cannot implicitly convert type error from the compiler. Why? Well imagine a scenario where that code did compile. You could do something like this:

List<Car> cars = [new Car(), new Car(), new Car()];
List<Vehicle> vehicles = cars;

vehicles.Add(new Bike());

					

And that certainly can't work. Casting an object doesn't physically change its implementation, so a List<> collection which stores Car can't magically start to contain Bike even if it has been cast to List<Vehicle>.

But the book describes an interesting scenario for a data structure where this can work. If the problems come from being able to add stuff to the collection, you can sidestep some of the problem with an approach using immutable data structures.

The basic collection url copied!

The book gives a simple implementation example of a stack. The initial class looks like:

interface IImStack<T> : IEnumerable<T>
{
    IImStack<T> Push(T item);
    T Peek();
    IImStack<T> Pop();
    bool IsEmpty { get; }
}

class ImStack<T> : IImStack<T>
{
    private class EmptyStack : IImStack<T>
    {
        public EmptyStack() { }
        public IImStack<T> Push(T item) => new ImStack<T>(item, this);
        public T Peek() => throw new InvalidOperationException();
        public IImStack<T> Pop() => throw new InvalidOperationException();
        public bool IsEmpty => true;
        public IEnumerator<T> GetEnumerator()
        {
            yield break;
        }
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
    public static IImStack<T> Empty { get; } = new EmptyStack();
    private readonly T item;
    private readonly IImStack<T> tail;
    private ImStack(T item, IImStack<T> tail)
    {
        this.item = item;
        this.tail = tail;
    }
    public IImStack<T> Push(T item) => new ImStack<T>(item, this);
    public T Peek() => item;
    public IImStack<T> Pop() => tail;
    public bool IsEmpty => false;
    public IEnumerator<T> GetEnumerator()
    {
        for (IImStack<T> s = this; !s.IsEmpty; s = s.Pop())
            yield return s.Peek();
    }
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

					

There's an interface to describe what the collection can do, a main class for the collection type and a private child class to express the "collection is empty" special case of the interface.

It's immutable because there's no Array or List here - you can't change the collection in any given instance. Modifications come from returning a new object - where the original has been modified by the Pop() and Push() methods. Such as:

var carStack = ImStack<Car>
                   .Empty
                   .Push(new Car())
                   .Push(new Car());

					

But so far this still suffers from the same problem as above - you can't cast this to ImStack<Vehicle> without getting compiler errors.

However the changes necessary to make this covariant are surprisingly small. (Well surprisingly small to me, at least...)

Making it covariant url copied!

You change the interface for IImStack to have out T as its generic type. The out keyword here tells C# that you plan to enable covariance for the type. But it's only applicable to interfaces, not the concrete classes. Then you remove the Push() method from the interface definition and from the ImStack<> class:

interface IImStack<out T> : IEnumerable<T>
{
    //IImStack<T> Push(T item); -- removed this method from the interface
    T Peek();
    IImStack<T> Pop();
    bool IsEmpty { get; }
}

					

But the collection would be a bit useless without the ability to push new values onto the stack, so you replace it with a new static method for Push() instead:

public static IImStack<T> Push(T item, IImStack<T> tail) => new ImStack<T>(item, tail);

					

That's separated the generic type parameter out - it can now be different between the core collection and the static method.

And finally we add an extension method which calls that static method to make usage of this revised Push() look seamless again:

static class Extensions
{
    public static IImStack<T> Push<T>(this IImStack<T> stack, T item) => ImStack<T>.Push(item, stack);
}

					

And with that in place, we can write:

IImStack<Car> cars = ImStack<Car>.Empty.Push(new Car()).Push(new Car());
		
IImStack<Vehicle> vehicles = cars;

IImStack<Vehicle> plusBike = vehicles.Push(new Bike());	

					

And this can compile and run. Using LinqPad's Dump() method to display the result, we now have a collection that starts off explicitly for the Car type but ends up containing both that and Bike after being cast to holding Vehicle:

Covariance achieved!

Conclusions url copied!

The book itself describes this concept of "factor the mutation out of the collection to enable covariance" as a less appreciated approach. And that seems true to me - I'd not seen this before. But it's fascinating, and is one of those things I'll be filing away at the back of my mind for the future...

Oh, and if this is interesting to you I'd recommend reading the book too.

↑ Back to top

• Feel like sharing?
• ⇒ On BlueSky
• ⇒ On LinkedIn
• ⇒ On Mastodon
• ⇒ On Email
• ⇒ QR Code

Nerding out about covariance and immutability

Close dialog