Why can't the Java compiler infer Iterable from the constraints "Iterable and () -> (Iterator)"?

Question

Background: I recently wrote an answer where I suggested writing the following code:

Files.write(Paths.get("PostgradStudent.csv"),
        Arrays.stream(PGstudentArray).map(Object::toString).collect(Collectors.toList()),
        StandardOpenOption.CREATE, StandardOpenOption.TRUNCATE_EXISTING);

After some thoughts, I went: "I don't actually need a list here, I just need an Iterable<? extends CharSequence>". As Stream<T> has a method Iterator<T> iterator(), I then thought, well, that's easy:

Iterable<? extends CharSequence> iterable = () -> Arrays.stream(arr).map(Object::toString).iterator();

(I extracted it to a local variable for this question, I would like to do it inline at the end.) Unfortunately this does not compile without additional type hints:

error: incompatible types: bad return type in lambda expression
Iterable<? extends CharSequence> iterable = () -> Arrays.stream(arr).map(Object::toString).iterator();
                                                                                                   ^
    Iterator<String> cannot be converted to Iterator<CharSequence>

Of course adding some type hints will make this work:

Iterable<? extends CharSequence> iterable2 = (Iterable<String>) () -> Arrays.stream(arr).map(Object::toString).iterator();
Iterable<? extends CharSequence> iterable3 = () -> Arrays.stream(arr).<CharSequence>map(Object::toString).iterator();

In my understanding, the Java compiler does the following things:

1. It looks at the target type of the expression, which is Iterable<? extends CharSequence>.
2. It then determines the function type of this interface, which is () -> Iterator<? extends CharSequence> in my case.
3. It then looks at the lambda and checks whether it is compatible. In my case, the lambda has a type of () -> Iterator<String>. Which is compatible with the function type determined in step 2.

Interestingly, if I change the target of the lambda to Supplier:

Supplier<Iterator<? extends CharSequence>> supplier = () -> Arrays.stream(arr)
    .map(Object::toString)
    .iterator();

it will compile fine.

Why can't javac infer the correct type for this lambda?

Answer 1

You can find some explanation here:

Wildcard-parameterized functional interface types must be turned into a function type (method signature) before checking for compatibility ... This works as follows:

Iterable<? extends CharSequence> becomes () -> Iterator<CharSequence>

So, if the lambda expression is implicitly-typed, the LHS becomes Iterator<CharSequence> while the RHS is Iterator<String>. Hence, an error:

Iterator<String> cannot be converted to Iterator<CharSequence>

This behavior is also explained in the JLS §18.5.3.

Answer 2

After reading the other answer (which is absolutely correct) and some coffee, it seems the explanation in the bug is pretty logical.

There are two cases here: an explicit lambda type and an implicit lambda type. The explicit type is :

Iterable<String> one = () -> Arrays.stream(arr).map(Object::toString).iterator();
Iterable<? extends CharSequence> iterable = one;

or as in the OP's example:

Iterable<? extends CharSequence> iterable2 = (Iterable<String>) () -> Arrays.stream(arr).map(Object::toString).iterator();

We are directly telling to the compiler which type the lambda expression is : Iterable<String>.

In this case the compiler has one thing to do only: see if the target is assignable to that type; pretty easy to find out and not very much related to lambdas per-se.

The other type is an implicit type, when the compiler has to infer the type and things get a bit tricky here. The "tricky" part comes from the fact that the target uses wildcards, thus could match more than just one option. There could be an infinite number of ways (finite of course, but just to prove a point) that the lambda could be inferred as.

It could start with something like this for example:

Iterator<? extends Serializable> iter = Arrays.stream(arr).map(Object::toString).iterator();

No matter what further gets done, this will fail: CharSequence does not extend Serializable, but String does; we will not be able to assign Iterable<? extends CharSequence> iterable to "whatever-the-infered-type-with-Serializable-is".

Or it could start with:

Iterator<? extends Comparable<? extends CharSequence>> iter = Arrays.stream(arr).map(Object::toString).iterator();

So theoretically the compiler could just start to infer what that type could be and check one by one if a "certain" inferred type could match the target; but requires a lot of work, obviously; thus not done.

The other way is a lot easier, "cut" the target and thus drop the possibilities of inference to just one. Once the target is transformed to:

Iterable<CharSequence> iterable...

the work that a compiler has to do is far more simple.

This, btw, would not be the first time I see this implicit vs explicit types logic in lambdas.