A Complete Guide to Variance in Java and Scala
This text aims to explain variance in type parameters both in Java and Scala. There is already a lot of material on this subject in various blogs and articles, but to me, they always felt either too complex, diving straight into advanced features and is hard to follow for someone new to the topic, or too simplistic and merely scratching the surface.
So, here’s my attempt at filling that gap.
First, a little background
I assume most (or all) of you are well acquainted with the concept of polymorphism in object-oriented programming. It’s cool to be able to e.g. test if an array is equal to another array, but without implementing the equality method for each and every type of array.
We just want to use the equals() method (assuming it’s defined for every object, which is true for Java and Scala) and we don’t want to care which exact type of object is actually contained in an array.
In Java, Integer[] is a subclass of Number[], and they are both subclasses of Object[]. This is called covariance. Given A <: B (meaning A is a subclass of B), if T[A] <: T[B] then T is covariant in its type. Given the same relationship A <: B, if T[B] <: T[A] then T is contravariant in its type.
If this is the first time you heard about contravariance it probably doesn’t make much sense to you right now, but wait until the end of this article. Finally, if T[A] and T[B] have no relationship despite the fact that A <: B, then we say T is invariant in its type.
By the way, if you looking for resources to learn Scala then I suggest you check out the Scala and Functional Programming for Beginners | Rock the JVM course on Udemy to start with. It’s a nice course for beginners who are both new to Scala and Functional programming.
So, arrays are covariant in Java. We can have a method isEqual() or sort() or shuffle() that takes an array of objects and we can pass in whatever array we want. Yay! We can also define a method taking an array of e.g. geometric shapes and pass in array of GeometricShapes, or Triangles, or EquilateralTriangles, and so on. Polymorphism at its finest.
Well, it comes at a price. Let’s say we have an array of integers. This is a subclass of an array of objects, right? So if I have a variable called “objectArray” that is an array of objects, it’s perfectly valid to assign our array of integers to objectArray.
Now we have a variable objectArray that is seen by the compiler as an array of objects, but underneath what we really have is an array of integers. OK, this is not a big problem… yet. But, our array of integers is now an array of objects in the eyes of the compiler! We are allowed to store strings and triangles and bananas — the compiler will just stand there and allow it to happen. Of course, at runtime our code will crash and burn when we get stuff from the original variable holding an array of integers (or, more precisely, variable which *thinks* it’s still holding an array of integers while in reality it’s holding all kinds of stuff).
We have encountered a problem. But what to do? There’s no turning back now (we’re talking 2004) because there are already thousands and thousands of commercial projects around the world using Java. Arrays will have to remain “hackable”. But, there was this cool new thing called generics coming up in Java 5. As you probably already know, they are written inside <> in Java, while Scala uses [] notation. Generics allow any class to have a type tag just like an array does, but unlike arrays, these type tags are not covariant.
So, in Java, MyClass<String> is not a subclass of MyClass<Object>. That’s great, generics can’t crash and burn! But yes, that means we don’t have that neat little polymorphism feature that we had with arrays. Method that takes MyClass<Object> cannot be passed an instance of MyClass<String>. We also can’t pass a List of Strings where List of Objects is needed. That’s a shame. We can always force some ugly casting, but that can be dangerous in the runtime (bringing us back to what we hated about arrays) and is considered a big no-no.
Bounds to the rescue
There is a way to achieve polymorphism (that is, covariance and contravariance) in this situation — by using bounded wildcards. There are two types of bounds for wildcards — upper bounds and lower bounds. Upper bound allows one to restrict the type “from above”, that is, to specify what’s the highest level of hierarchy allowed, while lower bound restricts the type “from below” by specifying what’s the lowest type that’s allowed. Here’s an example of an upper bounded wildcard:
public void process(List<? extends Car> list) { ... }This means that process() accepts List parameterized by Car or any subclass of Car. Yay, covariance! And if we switch extends with super, it becomes a lower bound:
public void process(List<? super Car> list) { ... }Now process() only accepts Lists parameterized by Car or any superclass of Car, thus achieving contravariance.
Good. We have the polymorphism we wanted. We have a method process() whose argument can be covariant or contravariant in its type, depending on whether we use upper or lower bounded wildcard. Note that bounds in Java are not just available for wildcards, but also for type parameters, so we can declare a class such as MyClass<T extends Car>. Type parameter (such as T) is different from wildcard (denoted by ?) in sense that it can be reused in the rest of the code. There are two major differences in bounded type parameters compared to bounded wildcards:
- With type parameters you can specify more than one bound. But since in Java you can only extend one superclass, other bounds specify the interfaces that must be implemented. For example, MyClass<T extends Bird & CanSwim & CanRun> means that type parameter for an instance of MyClass must extend Bird and implement CanSwim and CanRun.
- Only upper bounds can be used for type parameters. This means that MyClass<T extends Bird> is OK, but MyClass<T super Bird> won’t compile. Reasons for that are beyond the scope of this (already lengthy enough as it is) article, but we won’t be using bounds on type parameters anyway so I guess that’s OK. Let me just add that in Scala you can have both upper and lower bounds on type parameters, written as [T <: Bird] and [T >: Bird] respectively.
Let’s get back to bounds on wildcards since they do provide us with both covariance and contravariance. We achieved polymorphism and are able to provide our process() method with subtypes or supertypes of List<Car>, depending on whether we declared the list parameter as covariant (using upper bound) or contravariant (using lower bound). Now, there are some important limitations when using bounded wildcards that must be considered: we can only get stuff from the covariant list, and we can only put stuff in the contravariant list. Actual rule is a bit more general since the parameterized class could be anything, not just a List-like container. It goes like this: we can only use the covariant type parameter as a return type, and we can only use the contravariant type parameter as an input type. Let’s explain this on the List get-put example.
In case of covariant List<? extends Car> (also known as upper bounded list), we know that there are instances of Car inside. Some are sports cars, some are limos, maybe we also have further subclasses (e.g. AstonMartin), but they’re all cars. We can get objects from that list and know that what we’re getting is a Car. However, since we don’t know what the actual underlying type is (Car or SportsCar or AstonMartin), if such a list were to allow stuff to be put inside, then we would have the same problem as with arrays. We could create a list of sports cars, safely assign it to a List<Car> variable and then “safely” (as far as compiler is concerned) put limos inside. At runtime we would crash and burn again. The only thing we are allowed to put is null because it extends everything so whatever the actual underlying type is — null extends it.
On the other hand, in case of contravariant List<? super Car> (also known as lower bounded list), we know that it’s safe to put cars inside (this includes subtypes such as AstonMartin; they are also cars). Whatever the actual underlying type may be (e.g. a Vehicle or AnyRef), every Car extends it, so if we put an AstonMartin when actual underlying type is a Vehicle — we did nothing wrong, did we? AstonMartin is a Vehicle. But the situation is now opposite than with the upper bound — while we can put cars, we can’t get anything from this list (actually, we can, but it will be of type Object which is not very useful). We can’t get a Car because if the underlying type is, say, a Vehicle, then we would be in trouble. We don’t know what the actual underlying type is — for all we know, List could also be full of motorcycles, tractors and amphibious ATVs. Getting an object of type Car from that list could potentially cause a runtime exception.
Here’s all that in code:
List<? extends Integer> a = new ArrayList<Integer>();
List<? super Integer> b = new ArrayList<Integer>();a.add(3); // fails; let’s try with null
a.add(null); // works
b.add(3); // no problem hereInteger ai = a.get(0); // no problem here either
Integer bi = b.get(0); // fails; let’s try with Object
Object o = b.get(0); // works
You can also think of it this way: in both cases, you can only put lowest (most specific) allowed type and you can only get highest (most general) allowed type. For covariant (upper bounded) lists, the lowest allowed type is null and highest is Car, whereas for contravariant (lower bounded) lists lowest allowed type is Car and highest is Object
upper bound lower bound
null ------------------- Car ------------------- ObjectOK, so we can only get stuff from a covariant list and we can only put stuff into a contravariant list. This is called a get-put principle. Now let’s go back to the more general rule:
- use covariance for methods which return a generic type
- use contravariance for methods which take a generic type
- use invariance for methods which both accept and return a generic type
Quick recap: Arrays in Java are covariant, which allows dirty stuff that makes our code crash and burns. Generic (we can also call them parameterized) classes are invariant, which makes them immune to crashing and burning, but we lose polymorphism. We can achieve covariance and contravariance (and bring back the polymorphism) for each method through the usage of wildcard bounds, but when defining variance for a method we must keep the get-put principle in mind.
What about Scala?
First of all, in Scala, arrays are invariant, which removes the possibility of crashing and burning. As for lists, they are now covariant by default. They are safe to be covariant due to their immutability; there’s no danger of someone assigning a list of integers to a list of objects (since immutability disallows re-assignment; instead, every “add” operation on a List returns a new List). Immutability saved us from the ugly dilemma between losing polymorphism and crash-and-burn scenarios.
But let’s be honest here — this is not a major improvement. Arrays simply went for the lesser evil (instead of being prone to crash-and-burn, they now have no polymorphism), and lists became covariant just because they are immutable by default. One can also use immutable lists in Java (such as ImmutableList in Guava library) or implement their own, and go for covariance using upper bounds.
Real improvement is in the language itself. Java only supports use-site variance, which means that variance is defined when the type parameter is used. In practice this means that it is defined separately for each method using bounded wildcards.
Scala, on the other hand, supports both use-site variance (syntax is similar to Java, just replace <? extends T> with [_ <: T]) and declaration-site variance. Declaration-site, as the name suggests, means that variance is defined when the type parameter is declared. You can simply declare covariance by putting “+” in front of the type parameter, and “-” for contravariance (no sign means invariance).
So, in Java you would say:
public class Foo<T> { ... }
...
Foo<? extends Integer> covariantFoo = new Foo<Integer>();
Foo<? super Integer> contravariantFoo = new Foo<Integer>();Notice how Foo appears to be covariant in one case (covariantFoo) and contravariant in the other (contravariantFoo). It is not declared covariant or contravariant upfront; instead, its variance is defined at the point where it is used (use-site).
In Scala you can do the same thing, just with a somewhat different syntax (using [_ <: Integer] and [_ >: Integer] respectively), but you can also declare variance upfront (declaration-site):
class CovariantFoo[+T] { ... }
class ContravariantFoo[-T] { ... }
...
val covariantFoo = new CovariantFoo[Int]()
val contravariantFoo = new ContravariantFoo[Int]()This time we have two classes, each declaring its type parameter as being covariant or contravariant. Here’s a brief summary:
Covariance
if A is a subtype of B then:
Java: L<A> is a subtype of L<? extends B> (use-site)
Scala: L[A] is a subtype of L[_ <: B] (use-site)
L[A] is a subtype of L[+B] (declaration-site)Contravariance
if A is a supertype of B then:
Java: L<A> is a subtype of L<? super B> (use-site)
Scala: L[A] is a subtype of L[_ >: B] (use-site)
L[A] is a subtype of L[-B] (declaration-site)
Which approach is better, use-site or declaration-site? Well, neither is generally better. They are different ways to achieve something. I personally prefer declaration-site variance because it goes well with the whole “immutable therefore easy to reason about” functional paradigm (Scala also allows you to write in an imperative, non-functional way, but it is highly discouraged). Once you declare the variance of your type parameter(s), there’s no messing around them and changing them in the rest of the code.
Also, it’s better to put the burden of declaring variance on yourself since you are the designer; if you put that burden on the clients of your class, they may misuse it. To cite Programming in Scala [1]:
[With use-site variance] It will be the clients of the class that need to put in the wildcards, and if they get it wrong, some important instance methods will no longer be applicable. Variance being a tricky business, users usually get it wrong, and they come away thinking that wildcards and generics are overly complicated. With definition-site variance you express your intent to the compiler, and the compiler will double check that the methods you want available will indeed be available.
What exactly does Scala compiler double check? It checks if you are violating the rules of covariance and contravariance in your method definitions by using covariant types in contravariant positions and vice versa. Note that this is in direct relation to the get — put principle; it’s just a bit more generalized version of it. We could call it the covariant position — contravariant position principle. It says that covariant types can serve as method return types, but not as method parameter types, while it’s the other way around for contravariant types.
Let’s see an example. We could revisit our old example from the get-put; it claimed that, in case there was no get-put principle, “we could create a list of sports cars, safely assign it to a List<Car> variable and then put limos inside”. Now, since Scala favors immutable values, this wouldn’t be so bad. Our old list of sports cars would remain a list of sports cars, while the new list would be a list of all kinds of cars. There’s no danger of adding limos to a sports-cars-only list. So let me use a better example for the rules of covariance and contravariance.
If Foo[T] is covariant in its type T, that means we can treat some Foo[SportsCar] as a Foo[Car], right? OK, but if Foo[SportsCar] is a subclass of Foo[Car], then it must support all methods from the Foo[Car] (and possibly add some of its own, more specific ones). Now, what if Foo has some method that uses the value of type T as its parameter (that is, in contravariant position)? This particular method would have no problem accepting a limo in Foo[Car], but now in Foo[SportsCar] all of a sudden it only accepts sports cars! We would have an invocation which works in a superclass (passing a limo to that method), but not in a subclass. This would be a violation of the whole subclass-superclass concept. Methods which return values of type T are OK since returning a sports car obeys the obligation from the superclass to return a car.
It’s the other way around for classes that are contravariant in its type. Passing T into methods would be OK — since Foo is contravariant in its type, it means that subclasses of Foo are all those that are parameterized by Car’s supertype, such as Foo[Vehicle] or Foo[Any]. Method taking a Car would, in that case, become a method taking a Vehicle or Any. This is OK. What must be obeyed is that methods taking a Car in original class must be able to take a Car in the subclass instead of narrowing it down as we saw in the SportsCar example. And this is indeed fulfilled. Any code that may be using Foo[Car]’s methods to feed it with cars will also work if we substitute Foo[Car] for one of its subclasses, such as Foo[Vehicle]. Feeding cars to a method taking a Foo[Vehicle] is just fine.
But now in the case of Foo being contravariant we run into problems when we want to have a method return a value of type Car. In case of covariance, it would return limos, sport cars, AstonMartins etc. and they are all, in fact, cars. However, being a Foo[Car] and having your subclass return a Foo[Vehicle] (don’t forget that Foo is contravariant so its subclass must be parameterized by Car’s supertype) wouldn’t be quite right, because the whole point of having a subclass is that you can plug it in at any place where its parent class is needed, and that wouldn’t be possible in this case. Using a subclass such as Foo[Vehicle] would restrict the results of our method calls to vehicles, which means our old code would no longer work (perhaps it invokes “slam the door” on the result, but what it really got as a result was a motorcycle; method only promised us with a vehicle, remember?). Don’t worry if this is kind of hard to digest. It really isn’t a trivial thing to wrap your mind around. In the next section I will provide a richer example for contravariance and things should fall into place by the time you’re done with this article.
Back to our rules. So, declaration-site variance allows the compiler to check if rules of covariance and contravariance are obeyed. If you use use-site variance, however, your compiler cannot help you with these rules since it doesn’t know whether your class is covariant or contravariant in its type (or each of its types). The variance declaration is postponed until the point where the class is used. This means that you, as a designer of the class, have no control over these things. You will define your class methods and you will pray that future users of your class will invoke get-like methods only when they instantiate your class as covariant and invoke put-like methods only when they instantiate it as contravariant. The covariance/contravariance hassle is now on their hands. I don’t know about you, but I prefer to take this ugly work on myself and make their lives easier.
In the next (and final) section I will provide an example for variance in Scala by subtyping a function. Functions in Scala are first-grade citizens; not only can they be passed around as parameters, returned from methods, held in collections etc., but they can also be subtyped and supertyped. So instead of just having subclasses and superclasses, you can also have subfunctions and superfunctions!
Variance in function subtyping
Each one-parameter function in Scala is actually an implementation of Function1 trait (in reality it’s a bit more complicated, but details are omitted here for brevity):
trait Function1[-S, +T] { def apply(x: S): T }Notice that Function1 is contravariant in S and covariant in T. Some implementation of Function1 trait (let’s call it MySubFunction[S1, T1]) is a subclass of another (let’s call it MySuperFunction[S2, T2]) only if it obeys the variance rules provided in Function1 (that is, if S2 <: S1 and T1 <: T2).
This rule of function being covariant in its input type and contravariant in its return type comes from the Liskov substitution principle (LSP). It says that T is a subtype of U if it supports the same operations as U and all of its operations require less (or same) and provide more (or same) than the corresponding operations in U (subtyping is reflexive so S <: S).
OK, let’s see what that means. Think of a function:
def getCarInfo: Car => AnyRefThese are all valid sub-types of getCarInfo:
- Car => AnyRef
- Vehicle => AnyRef
- Car => String
- Vehicle => String
They all require less (or same) and provide more (or same) as Car => AnyRef. “Less” means “more general” and “more” means “more specific”. This is very logical: Vehicle is “less than” Car because we know less of the object (we only know that it’s a vehicle, but not which kind of vehicle), whereas it is “more than” AnyRef because it provides us with more than just an AnyRef object (we have all the fields and methods defined in Vehicle).
Let’s take a closer look at these four subtypes. First one is exactly the same as getCarInfo, and that’s OK because subtyping is reflexive (that’s why I added “or same” after less/more in the definition of LSP); second one requires less, because it doesn’t restrict us to just cars — it allows any vehicle, which is a lesser requirement than cars; third one provides more, because instead of providing us with just an AnyRef, it provides us with a much richer type String; and the fourth one both requires less and provides more than getCarInfo.
Stop and think about it for a second. This is covariance and contravariance in its full glory! If I want function B to be a subtype of function A, then B’s input parameter must be a superclass of A’s input parameter (contravariance) and B’s return value must be a subclass of A’s return value (covariance).
Let’s build a full example now. Here’s the code:
1 /**
2 * Remember! In Scala, every function that takes one argument
3 * is an instance of Function1 with signature:
4 *
5 * trait Function1[-T, +S] extends AnyRef
6 */
7
8 class Vehicle(val owner: String)
9 class Car(owner: String) extends Vehicle(owner)
10
11 object Printer {
12
13 val cars = List(new Car("john"), new Car("paul"))
14
15 def printCarInfo(getCarInfo: Car => AnyRef) {
16 for (car <- cars) println(getCarInfo(car))
17 }
18 }
19
20 object Customer extends App {
21
22 val getOwnerInfo: (Vehicle => String) = _.owner
23
24 Printer.printCarInfo(getOwnerInfo)
25 }Look at the method printCarInfo (line 15) that takes a function Car => AnyRef as a parameter:
def printCarInfo(getCarInfo: Car => AnyRef)If we are to invoke this method from our custom code (line 24), we must either pass a function with the identical signature (Car => AnyRef), or a function that’s a subtype of Car => AnyRef, that is, which requires less or same and provides more or same as Car => AnyRef. In the example we go for the second option and pass in a function (defined in line 22) that requires less than Car (a Vehicle) and provides more than AnyRef (a String):
val getOwnerInfo: (Vehicle => String) = _.ownerGood, LSP is satisfied, so our function Vehicle => String is a valid subtype of Car => AnyRef.
Method printCarInfo uses the function getCarInfo in line 16 to get info from a car and print it out. Even if printCarInfo code was not available to us and we couldn’t see inside the method, we would still know that it must be feeding cars (don’t forget that this also includes subtypes, e.g. AstonMartin) to getCarInfo. Its signature tells us that. So if we say that our substitute function for getCarInfo takes a Vehicle, we didn’t break anything, since all cars and their subtypes are also vehicles. All we did was that we provided a function that requires less, so printCarInfo will not notice anything different. What printCarInfo says is— “cool, whatever, as long as you provide me with a function that will accept my cars, I’m fine”. And a function that accepts vehicles surely accepts cars.
On the other hand, our Vehicle => String returns a String, which means it provides more. What printCarInfo said is that it wants a function returning an AnyRef. Is String an AnyRef? Yes, it is. Again, we didn’t break anything.
Great! We have shown that Vehicle => String is a perfectly valid substitute for Car => AnyRef. PrintCarInfo will continue its workflow normally without ever noticing that instead of Car => AnyRef it was provided a Vehicle => String instead. And we have seen contravariance, that weird little member of the variance family, in a real example instead of some esoteric theoretical explanation.
So there you have it. My attempt at explaining variance stops here. If you want to give me some feedback, feel free to contact me at sinisalouc@gmail.com.
References
[1]: Martin Odersky, Lex Spoon, Bill Venners, “Programming in Scala”, 2nd Edition
