Friday, July 01, 2011

Java Generics and Covariance/Contravariance

Suppose you have Java classes Animal, Mammal, and Giraffe, with the obvious relationships,

class Animal {…}
class Mammal extends Animal {…}
class Giraffe extends Mammal {…}

A coworker asked me why, if he had a method that accepted a List<Mammal>, why couldn't he pass into it a List<Giraffe>? Surely if a method was okay with operating on Mammals, it should be okay to operate on Giraffes, right?

Method declaration:
void petMammals(final List<Mammal> mammalsToPet);
Usage:
final List<Giraffe> myGiraffes = Collections.singletonList(new Giraffe());
petMammals(myGiraffes); // Complier doesn't let work

The answer to this riddle is that Java is designed to work with all kinds of generic classes, not just those which are collection-like. For instance, Comparator is a generic class, but you can't take a Comparator<Giraffe> and pass it to a method requiring a Comparator<Mammal>, since it doesn't know how to compare all Mammals. But you probably could pass a Comparator<Animal> to a method requiring a Comparator<Mammal>, since if it can sort Animals, it can certainly sort Mammals too.

So, since List and Comparator and every other generic class have to be treated the same way by the Java compiler, and it doesn't know for which uses it makes sense to allow for a larger type or smaller type to be passed in, you have to tell it each time. This requires learning the "wildcard type" syntax. Really understanding this syntax is key to writing methods that actually work the way you intend with your class hierarchy. For instance, our prior example really ought to be (with change in bold):

Method declaration:
void petMammals(final List<? extends Mammal> mammalsToPet);
Usage:
final List<Giraffe> myGiraffes = Collections.singletonList(new Giraffe());
petMammals(myGiraffes); // Now works!

That is, if you tell Java that you're okay with getting a List of a subtype, then Java will allow a List of a subtype in there. Even more interestingly, suppose that sorting Mammals is a common operation in your application, then you might have a method like:

void sortMammals(final List<? extends Mammal> mammalsToSort, final Comparator<? super Mammal> howToSort);

Which is quite clear that you can sort a List<Giraffe> with a Comparator<Animal>. A good example of a use of these wildcard types that's built into Java is the Collections.binarySearch method, which is itself parameterized on a type T, and allows for Lists of T's subtypes and Comparators of T's supertypes.

So, when writing a method that's using generics, it helps to take a second to think about what type you're really trying to use, and making your method actually have that type can solve a lot of confusion later on. Usually, classes which are collection-like can accept subclasses, and classes which are comparator-like can accept superclasses, but there are more reasons that one might be writing or using a generic class.

For further reading:
  • For those who love reading dry specifications of the internals of programming languages, section 4.5.1 of the Java Language Specification describes the details of how wildcard parameters work.
  • I'm constantly referring to Angelika Langer's Java Generics FAQs when I have questions like these. It has a lot of practical information on using generics in Java, without assuming a Computer Science degree or a love for academic type theory.
  • Eric Lippert, a developer for Microsoft who works on the C# compiler, had a whole blog series on covariance and contravariance in C#, explaining some of their thoughts as they were thinking about add some of these features to C#. I don't even develop in C#, but I found his explanations about the tricky parts of type systems very useful and interesting.

No comments: