Introduction

Subtyping is directly related to the Liskov Substitution Principle, which states that objects of a superclass shall be replaceable with objects of a subclass without affecting the correctness of that program. For example, if class B is a subclass of class A, then we should be able to replace A with B without disrupting the behavior of our program.

While covariant and contravariant are rules we use to determine the subtype relationship between two generic types. In our Exercise 2, we say this:

• Lists are covariant in their only type parameter.
• Functions are contravariant in the argument, and covariant in the result.

You see? When we mention covariance or contravariance, we must point out which type parameter of which generic type we are talking about. Let’s focus on covariance first.

Covariance and List Types

When we say that a type parameter of a generic type is covariant, it means that if there are two types S and T, where S is a subtype of T, then filling in this type parameter with S and T respectively maintains a subtype relationship of same direction.

First, let’s take a look at the first two questions. Banana is a subclass of Fruit, so Banana is a subtype of Fruit (written as Banana <: Fruit). We also know that the only type parameter of List is covariant. So when we fill Banana and Fruit into the type parameter of List, the resulting types List[Banana] and List[Fruit] still maintain the same direction of subtype relationship, that is, List[Banana] <: List[Fruit].

Using the same method, we can also determine the relationship between List[A] and List[B].

If you go to look at the documentation of Scala (c.f. List), or the code of the standard library, you will find that there is a + symbol in front of the type parameter of List.

sealed abstract class List[+A] extends // ...

The + indicates that type parameter A is covariant.

Covariance and Tuple Types

Similar to the List type, all type parameters of the Tuple type (regardless of how many type parameters it has) are covariant.

So I think you can also judge the relationship between the following types very quickly.

• (Banana, Fruit) and (Fruit, Fruit)
• (Banana, Juice) and (Fruit, Liquid)
• (Banana, Fruit) and (Fruit, Banana)

The key to solving the problem is to ensure that each type parameter of the two tuple types maintains the same direction of the subtyping relation. Don't forget that the subtyping relationship is reflexive, meaning that for any type T, we have T <: T.

It's not difficult to see that the relationships in the first two examples above are both <:, while the relationship in the last example is incomparable.

Function Types and Contravariance

Next, let's demystify the subtyping relation of function types. Many people find this challenging, but it's not really. First, the function type T => R can be written as Function1[-T, +R]. Here, the - symbol indicates that the type parameter T is contravariant.

Do you still remember how to determine the subtyping relation for Tuple types? If there are two types, (A1, B1) and (A2, B2), the subtyping direction of A1 and A2 needs to be the same as the subtyping direction of B1 and B2.

Now, with one type parameter of Function1 being contravariant and the other covariant, this means their subtyping relations must be opposite to derive the subtyping relation of Function1.

That is, given A1 => B1 and A2 => B2, there are two possible cases.

• (Case 1) If A1 <: A1 and B1 >: B2, then (A1 => B1) >: (A2 => B2).
• (Case 2) If A1 >: A1 and B1 <: B2, then (A1 => B1) <: (A2 => B2).

For other cases, A1 => B1 is not comparable with A2 => B2.

Apply What We’ve Learned

Let’s apply this to some questions!

• Banana => Juice and Fruit => Juice: Since Banana <: Fruit and Juice >: Juice, we have (Banana => Juice) >: (Fruit => Juice) (by applying Case 1).
• Banana => Juice and Banana => Liquid: Since Juice <: Liquid and Banana >: Banana, we have (Banana => Juice) <: (Banana => Liquid). (by applying Case 2).

The above two are both a piece of cake. Let's take a look at some challenging problems that leave some people confused. But they're actually not difficult; what we need to do is a step by step reasoning.

• (Fruit => Juice) => Liquid and (Banana => Liquid) => Liquid

  Let’s do this in three steps.

  1. We need to judge the relation between Fruit => Juice and Banana => Liquid. Since Fruit >: Banana and Juice <: Liquid, we have (Fruit => Juice) <: (Banana => Liquid) (by applying Case 2).
  2. We need to judge the relation between Liquid and Liquid, this is immediate. That is Liquid >: Liquid.
  3. By the conclusion of both 1 and 2, we have ((Fruit => Juice) => Liquid) >: ((Banana => Liquid) => Liquid) (by applying Case 2).

  Therefore, the answer is >:.

• Fruit => (Juice => Liquid) and Banana => (Liquid => Liquid).

  Similarly, let’s do this in three steps.

  1. The subtyping relation between types of function parameters are immediate, that is, Fruit >: Banana.
  2. Let’s see the subtyping relation between Juice => Liquid and Liquid => Liquid. Since Juice <: Liquid and Liquid >: Liquid, we have (Juice => Liquid) >: (Liquid => Liquid).
  3. The conclusion of both 1 and 2 matches neither Case 1 nor Case 2.

  Therefore, they are not comparable.

---

I hope this tutorial will be of help to you!