Type Inference And Generic Methods - [OOP & Java #7]
Tags: computerscience, oop, java, codenewbie
Published: 2020-09-28 09:22:52

_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. 
```java
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](https://dev.to/tlylt/generics-oop-java-5-2k46) and [Bounded wildcards](https://dev.to/tlylt/bounded-generic-types-wildcards-oop-java-6-1mcc)
- `Function<...>`
 - Functional interfaces (<small>will do an article about this soon</small>). 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?
```java
// 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);
```
---
![try-gif](https://media.giphy.com/media/XdreKrQI1LjcQ/giphy.gif)

---

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,
```java
// 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:
```java
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:
```java
// 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:
```java
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`:
```java
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...
```java
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`

```java
<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

```java
<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
```java
// 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
```java
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?
```java
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, (<small>note the following error because the error that we will be seeing in Q6 - 10 are only slightly different</small>):
```java
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**
```java
// 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
```java
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
```java
// 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.
```java
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](https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html). 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](https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html)