Hackle's blog
between the abstractions we want and the abstractions we get.
Hackle's blog
between the abstractions we want and the abstractions we get.
Have you ever noticed, in C# (or Java for that matter), IEnumerable<Subtype> can be assigned to IEnumerable<Supertype>, but not IList<Subtype> to IList<Supertype>? Well, that's co- and contra-variance in action.
Covariance is just a fancy way to say one thing changes in the same direction as another, and Contravariance, the opposite direction. For example, if 5 people are to evenly share some apples, then the more apples there are, the more apples each person will get. In this case, each person's share and total of apples are covariant, as they increase or decrease together.
Now if we fix the number of apples, say, we have 20 apples only, then the more people there are to share amongst, the fewer each person will get. In this case, each person's share and the number of people are contravariant , as when the latter increases, the former decreases, and vice versa.
In programming with types, convariance and contravariance appear in different forms.
A popular example of covariant is IEnumerable<T>. Say we have
public class Creature {}
public class Animal : Creature {}
public class Dog : Animal {}
And we can assign a value of IEnumerable<Dog> to a value of IEnumerable<Animal>.
IEnumerable<Creature> creatures = Enumerable.Empty<Creature>();
IEnumerable<Dog> dogs = Enumerable.Empty<Dog>();
IEnumerable<Animal> animals = dogs;
animals = creatures; // <-- this won't compile
Type Dog is assignable to Animal, so IEnumerable<Dog> is assignable to IEnumerable<Animal>, T and IEnumerable<T> change in the same direction, and are therefore covariant! We can also say that IEnumerable<T> is covariant in T.
You'd be thinking, if IEnumerable<T> is covariant in T, sure List<T> too? Well, not quite so. try,
List<Animal> animals = new List<Dog>();
It won't compile! The difference is that IEnumerable<T>, is actually defined as IEnumerable<out T>, and out here specifics that T is the type of output and is therefore covariant. What does out mean? Let's first let's look at Func<T> and Action<T>.
Func<T>Func<T> is defined as:
public delegate TResult Func<out TResult>();
See the out keyword? It's what makes Func<T> covariant in T. Now that you've seen IEnumerable<out T>, this example wouldn't be too surprising,
Func<Animal> findAnimal = new Func<Dog>(() => new Dog());
// not the other way around!
Func<Dog> findDog = new Func<Animal>(() => new Animal());
Here is an analogy: if I need a way to find an Animal, and am given a way to find a Dog, I am happy - a Dog is an Animal. However, if I need to find a Dog but am given a way to find any Animal, it's clearly no good.
Action<T>Action<in T> is the other way around. It's an easy guess that in means input.
Action<Dog> feedDog = new Action<Animal>(a => Console.WriteLine("come eat!"));
// this won't work!
Action<Animal> feedAnimal = new Action<Dog>(a => Console.WriteLine("come eat!"));
I need a way to feed a Dog, and am given a way to feed any Animal, I am happy. However, if I need a way to feed any Animal, but am given a way to feed only Dog, then it's no good.
This works for Func the same way, for example Func<in T, string>. In fact Action<T> is kind of like Func<T, void>. Of course C# won't allow using void as a type here - which is a bummer!
Analogies are nice, but what really is going on here? When in doubt, try code it. So here we go. Starting with Func:
Func<Animal> findAnimal = () => ?? must be animal
What happens if we only have a Dog at hand? It's
Func<Animal> findAnimal = () => new Dog() as Animal;
You'll note the upcast is not really necessary. Let's try Action next. First, Action<Animal> can act on Animal or its subtypes like Dog. Action<Dog> can act on Dog but not Animal. So how can we assign Action<Animal> to Action<Dog>? Let's say we have,
Action<Dog> feedDog => dog => Console.WriteLine("woof!");
Action<Animal> feedAnimal = animal => Console.WriteLine("I am full!");
And need to define,
Action<Dog> actOnDog => dog => ??
One option would be dog => feedDog(dog), or, if we have a Dog at hand, dog => feedAnimal(dog as Animal). Again the upcast is only for demonstration purpose.
Through coding it, we can see that it's nothing magic, but how type safety for sub-typing works through various composite types.
(This section is added on 2022-11-25)
This free upcast would seem frivolous but is important. As co- and contra-variance can be expressed simply as functions in Haskell. Covariance is post-composition, and contra-variance is pre-composition.
-- post composition
instance Functor (a ->) where
fmap :: (a -> b) -> (b -> c) -> a -> c
-- for illustration only, won't type-check as (->) :: a -> b and needs to be reversed
instance Contravariant (-> a) where
contramap :: (b -> c) -> (a -> b) -> a -> c
This may look unrelated to the type-level variance, but if we plug in our example, it becomes pretty obvious.
-- a free upcast as post-composition
(a -> Dog) -> (Dog -> Animal) -> (a -> Animal)
-- a free upcast as pre-composition
(Animal -> a) -> (Dog -> Animal) -> (Dog -> a)
(a -> Dog) is assignable to (a -> Animal) because there is a free upcast.
Similarly, (Animal -> a) is assignable to (Dog -> a), only with a pre-composition.
See, there are one and the same thing!
IEnumerable<T> vs IList<T>We know because T in IList<T> is not marked as out, so we can't assign IList<Dog> to IList<Animal>, the next question is, why can't we make it IList<out T> so such assignments become possible? Wouldn't that make our lives easier?
Let's assume that is possible, so we can do
IList<Animal> animals = new List<Dog>();
That looks innocent enough until we do
animals.Add(new Animal());
This doesn't make sense - animals is actually a List<Dog> and it cannot accept an Animal!
IEnumerable<T> is different - it does not support a Add method, in fact it has only one method IEnumerator<out T> GetEnumerator (). What's important here, is that the T also appears as return type. If we go one level deeper, IEnumerator<out T> also has only one getter, T Current { get; }, note T is the return type.
So what's the pattern here?
For an interface to be covariant in T, T must be used only as return type in its methods or properties.
IList<T> does not follow that rule - it has a method void Add<T>(T item) with T appearing as input type.
Another way to look at this is - an interface just groups Funcs or Action together. If T is covariant in all Funcs that use T, then and only then does it makes sense for T to stay covariant. Same goes for contra-variant.
Properties can be considered similarly. A getter is a Func<T> and a setter Action<T>.
There you go - that's why IList<T> and IEnumerable<T> behave differently. We call T in IList<T> invariant as it is neither co- nor contra-variant.
If we've made good sense this far, try take it one step further and read about positive and negative positions on this blog or explained in Haskell. Be warned, it can be a bit mind-bending!