What does "Recursive type bound" in Generics mean?
What is recursive type bound
This: <T extends Comparable<T>>
Note that the type parameter T is also part of the signature of the super interface Comparable<T>.
and how does the above piece of code help achieve mutual comparability?
It ensures that you can only compare objects of type T. Without the type bound, Comparable compares any two Objects. With the type bound, the compiler can ensure that only two objects of type T are compared.
There is an entry in the Java Generics FAQ written by Angelika Langer which explains the details of such declaration: http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html#FAQ106
To understand the concept of recursive type bounds, let's solve a simple problem. This concept is easier to understand by solving a real problem. I'll provide the definition of the recursive type bound at the end, because it makes more sense after understanding the concept.
Problem
Assume that we have to sort the fruits by their sizes. And we are told that we can only compare fruits of the same types. For example, we can't compare apples with oranges (pun intended).
So, we create a simple type hierarchy like following,
Fruit.java
interface Fruit {
Integer getSize();
}
Apple.java
class Apple implements Fruit, Comparable<Apple> {
private final Integer size;
public Apple(Integer size) {
this.size = size;
}
@Override public Integer getSize() {
return size;
}
@Override public int compareTo(Apple other) {
return size.compareTo(other.size);
}
}
Orange.java
class Orange implements Fruit, Comparable<Orange> {
private final Integer size;
public Orange(Integer size) {
this.size = size;
}
@Override public Integer getSize() {
return size;
}
@Override public int compareTo(Orange other) {
return size.compareTo(other.size);
}
}
Main.java
class Main {
public static void main(String[] args) {
Apple apple1 = new Apple(3);
Apple apple2 = new Apple(4);
apple1.compareTo(apple2);
Orange orange1 = new Orange(3);
Orange orange2 = new Orange(4);
orange1.compareTo(orange2);
apple1.compareTo(orange1); // Error: different types
}
}
Solution
In this code, we are able to achieve our objective of being able to compare the same types, that is, apples with apples and oranges with oranges. When we compare an apple with an orange we get an error which is what we want.
Problem
The problem here is that the code for implementing the compareTo() method is duplicated for Apple and Orange class. And will be duplicated more in all the classes that we extend from the Fruit, for creating new fruits in the future. The amount of repeated code in our example is less but in real world the repeated code can be of hundreds of lines in each class.
Moving Repeated Code to Common Class
Fruit.java
class Fruit implements Comparable<Fruit> {
private final Integer size;
public Fruit(Integer size) {
this.size = size;
}
public Integer getSize() {
return size;
}
@Override public int compareTo(Fruit other) {
return size.compareTo(other.getSize());
}
}
Apple.java
class Apple extends Fruit {
public Apple(Integer size) {
super(size);
}
}
Orange.java
class Orange extends Fruit {
public Orange(Integer size) {
super(size);
}
}
Solution
In this step, we get rid of the repeated code of compareTo() method by moving it to a superclass. Our extended classes Apple and Orange are no longer polluted with common code.
Problem
Here the problem is that we are now able to compare different types, comparing apples to oranges no longer gives us an error:
apple1.compareTo(orange1); // No error
Introducing a Type Parameter
Fruit.java
class Fruit<T> implements Comparable<T> {
private final Integer size;
public Fruit(Integer size) {
this.size = size;
}
public Integer getSize() {
return size;
}
@Override public int compareTo(T other) {
return size.compareTo(other.getSize()); // Error: getSize() not available.
}
}
Apple.java
class Apple extends Fruit<Apple> {
public Apple(Integer size) {
super(size);
}
}
Orange.java
class Orange extends Fruit<Orange> {
public Orange(Integer size) {
super(size);
}
}
Solution
To restrict comparison of different types, we introduce a type parameter T. So that the comparable Fruit<Apple> cannot be compared to comparable Fruit<Orange>. Note our Apple and Orange classes; they now inherit from the types Fruit<Apple> and Fruit<Orange> respectively. Now if we try to compare different types, the IDE shows an error, our desired behaviour:
apple1.compareTo(orange1); // Error: different types
Problem
But in this step, our Fruit class doesn't compile. The getSize() method of T is unknown to the compiler. This is because the type parameter T of our
Fruit class doesn't have any bound. So, the T could be any class, it is not possible that every class would have a getSize() method. So the compiler is right in not recognizing the getSize() method of T.
Introducing a Recursive Type Bound
Fruit.java
class Fruit<T extends Fruit<T>> implements Comparable<T> {
private final Integer size;
public Fruit(Integer size) {
this.size = size;
}
public Integer getSize() {
return size;
}
@Override public int compareTo(T other) {
return size.compareTo(other.getSize()); // Now getSize() is available.
}
}
Apple.java
class Apple extends Fruit<Apple> {
public Apple(Integer size) {
super(size);
}
}
Orange.java
class Orange extends Fruit<Orange> {
public Orange(Integer size) {
super(size);
}
}
Final Solution
So, we tell the compiler that our T is a subtype of Fruit. In other words, we specify the upper bound T extends Fruit<T>. This makes sure that only subtypes of Fruit are allowed as type arguments. Now the compiler knows that the getSize() method can be found in the subtype of Fruit class (Apple, Orange etc.) because the Comparable<T> also receives our type(Fruit<T>) that contains the getSize() method.
This allows us to get rid of the repeated code of compareTo() method and also allows us to compare the fruits of the same types, apples with apples and oranges with oranges.
Now the compareTo() method can be used inside the max() function given in the question.
Definition of a Recursive Type Bound
In generics, when a reference type has a type parameter that is bounded by the reference type itself, then that type parameter is said to have a recursive type bound.
In our example, the generic type Fruit<T extends Fruit<T>>, Fruit is our reference type, its type parameter T is bounded by the Fruit itself, so, the type parameter T has a recursive type bound Fruit<T>.
A recursive type is one that includes a function that uses that type itself as a type for some argument or its return value. In our example, compareTo(T other) is the function of the recursive type that takes the same recursive type as an argument.
Caveat
There is a caveat in this pattern. The compiler doesn’t prevent us from creating a class with a type argument of another subtype:
class Orange extends Fruit<Orange> {...}
class Apple extends Fruit<Orange> {...} // No error
Note in the Apple class above, by mistake we passed Orange instead of the Apple itself as a type argument. This results in the compareTo(T other) method to take Orange instead of Apple. Now we no longer get error while comparing different types and suddenly not able to compare apples with apples:
apple1.compareTo(apple2); // Error
apple1.compareTo(orange1); // No error
So, the developer needs to be careful while extending the classes.
That's it! Hope that helps.