C# Why can I not add a hashset typed to a subclass to a hashset typed to its superclass

Question

Why do I get a compile error in the following code (see line with comment)?

    public void Test()
    {
        HashSet<HashSet<Animal>> setWithSets = new HashSet<HashSet<Animal>>();
        HashSet<Cat> cats = new HashSet<Cat>();
        setWithSets.Add(cats); // Compile error
    }

    private class Animal { }

    private class Cat : Animal { }

VS2012 gives me two errors, the first one the important one:

• Error 2 Argument 1: cannot convert from 'System.Collections.Generic.HashSet<Expenses.Tests.TestDb.SetTest.Cat>' to 'System.Collections.Generic.HashSet<Expenses.Tests.TestDb.SetTest.Animal>'
• Error 1 The best overloaded method match for 'System.Collections.Generic.HashSet<System.Collections.Generic.HashSet<Expenses.Tests.TestDb.SetTest.Animal>>.Add(System.Collections.Generic.HashSet)' has some invalid arguments

My question is: Why can I not add "cats" to the "setWithSets"?

Answer 1

To better understand why this is not allowed, consider the following program.

The line setOfSets.First().Add(new Dog()); is acceptable to the compiler, because a collection of animals can surely hold an instance of Dog. The problem is that the first collection of animals in the collection is a collection of Cat instances, and Dog does not extend Cat.

class Animal { }
class Cat : Animal { }
class Dog : Animal { }

class Program {
    static void Main(string[] args) {

        // This is a collection of collections of animals.
        HashSet<HashSet<Animal>> setOfSets = new HashSet<HashSet<Animal>>();

        // Here, we add a collection of cats to that collection.
        HashSet<Cat> cats = new HashSet<Cat>();
        setOfSets.Add(cats);

        // And here, we add a dog to the collection of cats. Sorry, kitty!
        setOfSets.First().Add(new Dog());
    }
}

Answer 2

Even if Cat derives from Animal, it is not true that HashSet<Cat> derives from HashSet<Animal>. (The only base class of HashSet<Anything> is the object class.)

To get the behavior you want, the HashSet<T> generic type would need to be covariant in its type parameter T. But it is not, for two reasons:

1. In C#, only generic interfaces and generic delegate types can be co- or contravariant. HashSet<> is a class.
2. You can not only read from a HashSet<>, you can also add to it (and do other things). Therefore covariance is logically impossible. Or else one would be able to regard a HashSet<Cat> as a HashSet<Animal> and then add a Dog to it. But a set of cats does not allow dogs.

If you changed HashSet<T> into for example IReadOnlyCollection<T> (see .NET 4.5 documentation: IReadOnlyCollection<out T> Interface), things would work because the latter type (1) is an interface, (2) allows only reads, and (3) has therefore premitted a marking "I'm covariant in T" which the authors of the type decided to apply.