Suppose we have my usual hierarchy of types,
Giraffe, etc, with the obvious type relationships. An
IEqualityComparer<T> is contravariant in its type parameter; if we have a device which can compare two
Animals for equality then it can compare two
Giraffes for equality as well. So why does this code fail to compile?
IEqualityComparer<Animal> animalComparer = whatever; IEnumerable<Giraffe> giraffes = whatever; IEnumerable<Giraffe> distinct = giraffes.Distinct(animalComparer);
This illustrates a subtle and slightly unfortunate design choice in the method type inference algorithm, which of course was designed long before covariance and contravariance were added to the language.
Let's take a look at the signature of the
Distinct extension method that was used above:
public static IEnumerable<T> Distinct<T>( this IEnumerable<T> source, IEqualityComparer<T> comparer)
Type inference computes a set of bounds on what
T can be based on an analysis of each argument and its corresponding formal parameter type. For the first argument, since
IEnumerable<T> is a covariant interface, the type inference algorithm computes that
T must be
Giraffe or any larger type.1 The specification expresses this notion by saying that
Giraffe is a "lower bound" -- whatever is finally chosen has to be a type that is not smaller than
For the second argument, since
IEqualityComparer<T> is a contravariant interface, the type inference algorithm concludes that
T must be
Animal or any smaller type. This is an "upper bound" --
T has to be a type that is not larger than
Given these two bounds, what type should actually be inferred for
T? One of the design rules of C# that I have mentioned many times on this blog is that when given a set of types to choose from, C# always chooses one of those types rather than making up a type that is not in the set. So we know that we are going to choose either
Giraffe and not some third type which satisfies the constraints, like
Mammal. But which? Both types satisfy the bounds! Both
Giraffe are not smaller than
Giraffe, and both are not larger than
When faced with this situation the type inference algorithm chooses the larger of the types, so
T is inferred to be
Animal. Thus we have:
public static IEnumerable<Animal> Distinct<Animal>( this IEnumerable<Animal> source, IEqualityComparer<Animal> comparer)
and since the method returns
IEnumerable<Animal>, it cannot be assigned to a variable of type
You would be forgiven for expecting
Giraffe to be chosen because that's what the spec says:
If among the remaining candidate types Uj there is a unique type V from which there is an implicit conversion to all the other candidate types, then Xi is fixed to V.
That's a long-standing typo that has never been fixed in the spec; the intended wording was "to which", not "from which".
It might seem strange to choose the larger type here; why not choose the more specific type if you can? We designed the type inference algorithm for C# 3, which did not have covariance or contravariance2 and so it was a bit of a moot point; the spec said that in the unlikely event of a conflict, choose the larger type. When C# 4 came along and added contravariance I made the case that we ought to choose the more specific type, because now there were scenarios where it actually might work, but we ultimately decided to stick with the existing algorithm. We then promptly wrote that algorithm down wrong in the spec. Whoops.
In any event, this is a small problem. If it hurts when you do that then simply change the type of the comparer:
IEqualityComparer<Animal> animalComparer = whatever; // Legal thanks to contravariance: IEqualityComparer<Giraffe> giraffeComparer = animalComparer; IEnumerable<Giraffe> giraffes = whatever; IEnumerable<Giraffe> distinct = giraffes.Distinct(giraffeComparer);
And now there is no conflict; the bounds inferred are an upper bound of
Giraffe and a lower bound of
Giraffe, so there's only one to choose from.
- Recall that when I say that one type is larger than another, I mean that there is an implicit conversion from the smaller type to the larger type.
Animalis a larger type than
Animals, but some
Animals are not
Giraffes. There are more
Animalis the larger type. ↩
- Except for array type covariance. ↩