Type Inference And Generic Methods - [OOP & Java #7]

P.S. This article is written in response to an interesting question raised by someone else and that question solidified my understanding of Generics and wildcards.

Suppose we have the following:

• A Demo class that can hold a list of items.
• The items can be of any type specified by a client/caller.
• The Demo class has a map method that takes in a function and returns a new list of items in the original list but modified by that function.

import java.util.List;
import java.util.ArrayList;
import java.util.function.Function;

class Demo<T> {
  List<T> list;
  Demo(List<T> list) {
    this.list = list;
  }

  <U> Demo<U> map(Function<? super T, ? extends U> f) {
    List<U> answer = new ArrayList<U>();
    for (T item : this.list) {
      answer.add(f.apply(item));
    }
    return new Demo<U>(answer);
  }
}

Additional Infomation

• <T> , <? super T, ? extends U> etc.
  • Generics and Bounded wildcards
• Function<...>
  • Functional interfaces (will do an article about this soon). Suffice to say that they are single-method-only interfaces that are meant to make functions first-class-objects in Java. In here, a sample function that we are going to use below can be interpreted as follows: Function<Object, Integer> f = x -> x.hashCode(); f is a function that takes in an input of type Object and output an Integer.

Now, which of Q1 - 10 are able to compile without error?

// turns an input object into its hash value representation
Function<Object, Integer> f = x -> x.hashCode();

// List of strings
List<String> strings = new ArrayList<String>();
strings.add("a");
strings.add("b");

// Q1 - 5
Demo<Integer> list = new Demo<String>(strings).map(f);
Demo<Number> list = new Demo<String>(strings).map(f);
Demo<Object> list = new Demo<String>(strings).map(f);
Demo<String> list = new Demo<String>(strings).map(f);
Demo<> list = new Demo<String>(strings).map(f);

// Q6 - 10
(Demo<Integer>) new Demo<String>(strings).map(f);
(Demo<Number>) new Demo<String>(strings).map(f);
(Demo<Object>) new Demo<String>(strings).map(f);
(Demo<String>) new Demo<String>(strings).map(f);
(Demo) new Demo<String>(strings).map(f);

Answers
1 OK 6 OK
2 OK 7 ERROR
3 OK 8 ERROR
4 ERROR 9 ERROR
5 ERROR 10 OK

Analysis

Let's try to interpret the type parameters involved and that should clear things up.

When we create a Demo object using its constructor, we need to pass in a list that contains a certain type of item. The type of items becomes the type T in the Demo class. So,

// note that map() method is not applied here
// T is replaced by String
Demo<String> listOfString = new Demo<String>(Arrays.asList("a", "b"));

// T is replaced by Integer
List<Integer> myList = new ArrayList<Integer>();
myList.add(1);
Demo<Integer> listOfInteger = new Demo<Integer>(myList));

Effectively, Demo class looks like the following:

class Demo<String> {
  List<String> list;
  Demo(List<String> list) {
    this.list = list;
  }
//...
}

class Demo<Integer> {
  List<Integer> list;
  Demo(List<Integer> list) {
    this.list = list;
  }
//...
}

Remember that due the invariance relationship, the following is not allowed:

// ERROR
Demo<Number> listOfNumber = new Demo<Integer>(Arrays.asList(1, 1));

Now Let's look into Question 1 - 5

Questions with regards to assignment

Statements 1 to 5 are trying to do the following:

• Call the constructor of Demo and pass in a list of strings
• Call .map(f) method on the newly created instance and return a new Demo instance
• Assign the Demo instance into one of the declared variables.

The constructor

Demo<Integer> list = new Demo<String>(strings) .map(f);

No issues here, since we declare that T in Demo is String and we passed in a list of strings. So as far as the constructor is concerned, we are passing in an argument of the correct type and it will return us an instance of Demo<String>.

The map method

Demo<Integer> list = new Demo<String>(strings) .map(f);

This is where confusion sneaks in. Let's list out the important related code fragments:

Function<Object, Integer> f = x -> x.hashCode();

class Demo<T> {
  List<T> list;
  Demo(List<T> list) {
    this.list = list;
  }

  <U> Demo<U> map(Function<? super T, ? extends U> f) {
    List<U> answer = new ArrayList<U>();
    for (T item : this.list) {
      answer.add(f.apply(item));
    }
    return new Demo<U>(answer);
  }
}

We know that the instance that we are calling the method map from is of Demo<String>, from the preceding discussion on the constructor.

So when map is invoked, T in the Demo class is still String. Therefore we can view our Demo class with T replaced with String:

class Demo<String> {
  List<String> list;
  Demo(List<String> list) {
    this.list = list;
  }

  <U> Demo<U> map(Function<? super String, ? extends U> f) {
    List<U> answer = new ArrayList<U>();
    for (String item : this.list) {
      answer.add(f.apply(item));
    }
    return new Demo<U>(answer);
  }
}

Now, map method still has two "unknowns" :

• ?
• U

When we call the map method, we pass in a function f which will "supply" type to the map method, and they must agree for the method to accept f as an argument.

Let's compare them very closely...

Function<Object, Integer> f = x -> x.hashCode();
<U> Demo<U> map(Function<? super String, ? extends U> f)  

// for better visual, I will add spaces to align them
                Function<     Object,       Integer>
<U> Demo<U> map(Function<? super String, ? extends U>) 

Input

Object from the function f corresponds to ? super String in map's first parameter.
Guess what ? will be ...

• ? becomes Object.
• Hence Object super String
• Which is itself a valid statement as Object is indeed a parent of String

<U> Demo<U> map(Function<Object super String, ? extends U>)

Output

Integer from the function f corresponds to ? extends U in map's second parameter.
Guess what ? will be ...

• ? becomes Integer, which is unsurprising
• This is fine because ? is a wildcard and it can be of any type

<U> Demo<U> map(Function<Object super String, Integer extends U>)

Guess what U will be ...

Since nowhere is U explicitly stated, U will be inferred by the compiler.
How does it do the inference?

1. If the returned object is assigned to a declared variable, then U becomes the type specified by the assigned variable. OR
2. If the returned object is not assigned to anything, the compiler has nothing else to infer but the method argument, which is the ?

In our context

1. U becomes the type specified in the Left-Hand-Side(LHS) of the assignment statement. OR
2. U becomes the type that is in ?.

The Assignment

Finally, let's look at the individual questions

// Q1 - 5
Demo<Integer> list = new Demo<String>(strings).map(f);
Demo<Number> list = new Demo<String>(strings).map(f);
Demo<Object> list = new Demo<String>(strings).map(f);
Demo<String> list = new Demo<String>(strings).map(f);
Demo<> list = new Demo<String>(strings).map(f);

For Q1 - 4, by the logic of type inference, U will become Integer, Number, Object, String respectively.

Just to illustrate using Q2

Demo<Number> map(Function<Object super String, Integer extends Number> f) 

Note that Integer extends Number is itself a valid statement because Number is a parent of Integer.

So, focusing on the output, we could say that the method call in Q2 will return a Demo<Number> that will be assigned to Demo<Number> list, perfectly fine!

The same goes for Q1 and Q3.

Why is Q3 wrong?

Demo<String> map(Function<Object super String, Integer extends String> f) 

Replacing U with String, we get this contradiction:

• Integer extends String
• Invalid because String is not the parent of Integer.

The error provided by the compiler is quite clear, (note the following error because the error that we will be seeing in Q6 - 10 are only slightly different):

incompatible types: inference variable U has incompatible bounds, 
equality constraints: java.lang.String 
lower bounds: java.lang.Integer

Q5 is also a bad statement.
This is because we have to supply a type argument when we declare an object of a generic type.

Questions with regards to typecast

// Q6 - 10
(Demo<Integer>) new Demo<String>(strings).map(f);
(Demo<Number>) new Demo<String>(strings).map(f);
(Demo<Object>) new Demo<String>(strings).map(f);
(Demo<String>) new Demo<String>(strings).map(f);
(Demo) new Demo<String>(strings).map(f);

The main logic has been explained in the above section. The only difference here is that instead of assigning the returned object to a variable, we are only doing a typecast. Or, we are typecasting the returned object before it is being assigned to any variable.

Similar to Q1 - 5, we still need to infer what U is before we proceed to return something. Unlike the assignment statements, the compiler has no variables to infer from. Hence, it will engage the strategy number two, which is to infer from the method argument.

Remember that we have
map(<Object super String, ? extends U>)
So, the only thing to refer to is ?.
? has been established above to be Integer, and hence U must be Integer
Now we have

Demo<Integer> map(Function<Object super String, Integer extends Integer> f) 

Because U is Integer, the return type of the map method becomes Demo<Integer>.

Knowing that Generics are invariant, we will know that except Q6 (and Q10), the rest of the statements are problematic.

Illustrating using Q7

// ERROR
(Demo<Number>) Demo<Integer>  ...

// Or view it as 
List<Integer> listOfIntegers = new ArrayList<Integer>();
listOfIntegers.add(1);
listOfIntegers.add(2);
Demo<Number> list = new Demo<Integer>(listOfIntegers); 

The compiler error is now:

incompatible types: Demo<java.lang.Integer> 
cannot be converted to Demo<java.lang.Number>

For Q10, even though it compiles, it is not a good practice because we are assigning the returned object to its rawtype.

List<Integer> listOfIntegers = new ArrayList<Integer>();
listOfIntegers.add(1);
listOfIntegers.add(2);
// View it as 
Demo list = new Demo<Integer>(listOfIntegers); 

Now list is of type Demo.

Target Type & Type Witness

My explanations above did not make use of the technical terms introduced in Oracle's java tutorial. Here's how I would explain it using the right terminologies.

Demo<Number> list = new Demo<String>(strings).map(f);

• This statement (LHS) is expecting an instance of Demo<Number>
• Demo<Number> is the target type
• Because the method map(f) returns a value of type Demo<U>, the compiler infers that the type argument U must be the value Number
• Alternatively, we can also be explicit and state the type witness, right before the method name Demo<Number> list = new Demo<String>(strings).<Number>map(f);

References

Oracle's Java tutorial on Type Inference