Variance from Subtyping’s view

This concept has somehow got me intrigued on a few occasions and I am sure majority of the readers find this interesting too.

Let’s start with what is a “variance”? In simple terms, it is about allowing a type to be interpreted as another type, provided there is some (subtyping) relation between the two.

If type T is a subtype of type U , then T can be provided wherever U is expected.

T some_t = create_T();
U some_u = t;

which is:

Cat some_cat = create_cat("fluffy");
Mammal some_mammal = cat; 
Animal some_animal = mammal;
      // or 
Animal some_animal = cat;

As you can see above, from the subtyping relation (<:), we have:

T <: U
Cat <: Mammal <: Animal

Cat is a subtype of Mammal and then further also of Animal, and Mammal is a subtype of Animal. The relation is transitive.

The other way around it is called supertyping (>:). Animal is a supertype of Mammal & Cat and Mammal is a supertype of Cat.

Animal >: Mammal >: Cat

Covariance

So if we have a list of Cat, we can assign it to a type that is a list of Animal, or if we have a function that takes an Animal we can provide it a Cat .

Func (Animal a) {
    // blah blah
}
List[Cat] list_of_cats = create_list_of_cats();
Func(list_of_cats[0]);
List[Animal] = list_of_cats;

This is called Covariance. We can say that List[A] is covariant over A. i.e List[T] <: List[U] provided T <: U. You can give T to Func(U) , provided T <: U.

So we can say that covariance increases the “scope” of a type’s usage. Animal can be used “more widely” than Cat.

What would happen, if we could give Animal where Cat is expected. Let’s look at an example:

Dog dog = create_dog("max");
Animal animal = dog; //covariance
Cat cat = animal; //assuming this is allowed
cat.meow(); //**Error** 

As we can see, animal above is actually a Dog and obviously this is incorrect.

Dogs don’t meow!

Contravariance

This is a bit confusing to understand at start, but simple enough once you get the reasoning behind it.

Let’s consider we have a function Func(A) . So as a type, Func(A) is contravariant over it’s input argument(s).

i.e

If T <: U , then Func(U) <: Func(T) . Yes, you read it right. Not a typo. It basically says you can give Func(U) where Func(T) is expected.

Func(Animal) f_animal_input = provide_some_func_that_takes_animal();
Func(Cat) f_cat_input = f_animal_input;

Here, we are basically narrowing down the “scope” of the type’s usage. f_cat_input() is “less widely” usable than f_animal_input(). f_animal_input() obviously can take in any Animal. It’s just that we are now restricting it to only accept a Cat.

Now, let’s see what would happen if we were allowed to give Func(Cat) , where Func(Animal) is expected.

provide_some_func_that_takes_cat() {
   feed_the_cat (Cat c) {
      feed_whiskas (c)
   }
   
   return feed_the_cat;
}
Func(Cat) f_cat_input = provide_some_func_that_takes_cat();
Func(Animal) f_animal_input = f_cat_input;//assuming this is allowed
Dog dog = create_dog("max");
f_animal_input (dog); //**Error**

We are passing Dog to f_animal_input() which actually is fine, as per the covariance rules, since it is of type Func(Animal). But f_animal_input() is actually a Func(Cat). So essentially you have a function that’s suppose to handle aCat, now handle a Dog.

You don’t feed cat food to a dog!

Covariance, once more

So now that we understand that a function is contravariant over it’s input arguments. The next obvious question would be “Does contravariance also hold true for return arguments as well?”

Take a moment to think.

If your answer is no, then you are bang on!

Function is covariant over it’s return arguments. i.e you are allowed to give CreateCat() -> Cat where CreateAnimal() -> Animal is expected.

This should be easy to reason about. Just the way we think about a List[A] being covariant over A, Func() -> A is covariant over A too.

Invariance

This is relatively simple to understand. If there is no subtyping relationship between the types, then you cannot use one in place of another. You cannot give a Cat , where a Dog is expected, just like you cannot give aSpacecraft where an Orange is expected.

You see the point? If I am in Japan, then I will have to buy stuff there in Yen . I cannot carry transactions in Rupee, whereYen is expected. So that’s an invariant, which needs to be upheld.

Mutability & Variance

Let’s take a look at the covariance example we covered in the beginning. What if the List[A] was mutable?

1 MutableList[Cat] list_of_cats = create_mutable_list_of_cats(); 
2 MutableList[Animals] list_of_animals = list_of_cats; 
3 
4 Dog dog = create_dog("max");
5 list_of_animals.add(dog);
6
7 feed_the_cats(list_of_cats);  // feed_the_cats(List[Cat])

If you read the carefully, there are a few problems in the above code. Let’s break it down:

• We create a mutable list of Catand assign to mutable list of Animal , as per the covaraince rules.
• We then add a Dog to the list_of_animals , since Dog is an Animal. See the problem yet?
• Further we pass list_of_cats to the function feed_the_cats() . Now this where we hit a problem. The list_of_cats being mutable was added a Dog as list_of_animals on line no. 5. But feed_the_cats() , expects a List[Cat] , which is not truly a List[Cat] anymore, as we have added a Dog to it.

But the code seems fine, as it “seems” to obey the variance rules. Well, not really. The line no. 2 above is actually problematic. SomeType[A] can be covariant over A , provided SomeType is immutable, otherwise it is invariant. So in the above case MutableList[A] is invariant over A and the statement MutableList[Animals] list_of_animals = list_of_cats; is actually incorrect. We cannot treat MutableList[Cat] as a MutableList[Animal] .

Closing Points

Well, I hope this helped in understanding a point or two about variance and subtyping. You won’t have to dealt with these concpets in your everyday programming, but nontheless are one of the very important aspects of understanding types in general.

Special mention: Although this video is based on Rust, I found it very helfpul in understanding the concept better.