Why is Java unable to infer the type when comparing Map.Entry objects?

Question

Why does the following cause a compilation error?

One

Map<Integer, Integer> map = new HashMap<>();
    List<Integer> numList = map.entrySet().stream()
            .sorted(Comparator.comparing(Map.Entry::getValue).reversed())  //this part
            .map(Map.Entry::getKey)
            .toList();

Error:

java: incompatible types: cannot infer type-variable(s) T,U
(argument mismatch; invalid method reference
  method getValue in interface java.util.Map.Entry<K,V> cannot be applied to given types
    required: no arguments
    found:    java.lang.Object
    reason: actual and formal argument lists differ in length)

But why are the following snippets working fine?

Two

Map<Integer, Integer> map = new HashMap<>();
    List<Integer> numList = map.entrySet().stream()
            .sorted(Comparator.comparing(Map.Entry<Integer, Integer>::getValue).reversed())
            .map(Map.Entry::getKey)
            .toList();

Three

Map<Integer, Integer> map = new HashMap<>();
    List<Integer> numList = map.entrySet().stream()
            .sorted(Comparator.comparing(Map.Entry::getValue))
            .map(Map.Entry::getKey)
            .toList();

It seems like sorted() needs a Comparator<Map.Entry<Integer, Integer>. But why are no generics needed in case Three? Does Java infer the type Map.Entry<Integer, Integer>? If so, why can't Java infer the type in case One?

Answer 1

It's.. complicated.

I just want to get on with it

The short answer is: Because the specification says so and it's unlikely to change anytime soon. You will simply have to ensure the type system knows what the full type of that function is, which you can do with explicit <Integer, Integer> as you did in snippet 2, or by assigning the function first:

Function<Map.Entry<Integer, Integer>, Integer> entryToValue = Map.Entry::getValue;

var map = new HashMap<Integer, Integer>();
List<Integer> numList = map.entrySet().stream()
            .sorted(Comparator.comparing(entryToValue).reversed())
            .map(Map.Entry::getKey)
            .toList();

That's probably not what you were looking for (the above is quite a bit longer and still effectively requires a whole bunch of types in <>; you cannot just replace that very first variable declaration with var).

I want to know why

The way lambdas (either :: or -> based) work in Java is that the concept does not itself have any type. We can witness this:

Object o = () -> System.out.println("Hello, World!");

Does not compile.

Instead the way lambdas work in Java is that they must be 'retrofitabble' into a so-called "functional type", and they simply are that. Which is why this does work:

Runnable r = () -> System.out.println("Hello, World!");
// or
Object o = (Runnable) () -> System.out.println("Hello, World!");

But, lambdas also allow you to omit the variable name. You can write:

Consumer<String> printer = x -> System.out.println(x);

and you do not have to write String x there. You can just leave it. But, x is a string. The compiler 'figured it out'. It can only do that if it already knows that functional type.

Inside out, outside in

Ordinarily expressions are resolved inside out. Take 2 + 2 for example. In Java, + has 2 completely, totally unrelated meanings: 'add 2 numbers together' and 'concatenate 2 strings'. The compiler figures out which one you meant by working 'inside out'. If you write (foo.getBar().getBaz() + 5), it will first figure out what foo.getBar().getBaz() is, and only then figure out what that + means (it'd be string concat if getBaz returns a string, addition if it returns a number, and a compiler error if it returns anything else). In fact, this is turtles all the way down: To know what foo.getBar().getBaz() means, the compiler first figures out what foo.getBar() means and finally to figure that out, it figures out what foo is (what type it has), and only then does the compiler actually know what you tried to do there and can compile it.

But with lambdas, that cannot work. The compiler cannot look at x -> System.out.println(x) and figure out that this is a Consumer<String>. It can be many things. There are an infinite amount of types in existence that 'take 1 argument and return void'. From context we don't even know the type of x, so there's no possibility to delve in. In fact, imagine this:

class Example {
  static String method1(Integer x) { return ""; }
  static AtomicInteger method1(Boolean y) { return new AtomicInteger(); }
}

The code v -> Example.method1(v) - what is the signature of that? It's not possible to tell. It's perhaps a Function<Integer, String>, but it could also be a Function<Boolean, AtomicInteger>.

Hence, in lambdas specifically, javac must go outside in instead of the usual inside out. Javac needs to treat the entire lambda as a schrödinger's function, with no idea about the signature of it, and instead do work on the outside to attempt to figure it out, and only then can it go 'back' and work on the lambda again.

But this process is ambiguous. Imagine this situation:

void foo(Function<Integer, String> processor) {}
void foo(Function<Boolean, AtomicInteger> processor) {}

See footnote ^[1]

and then the Java code:

foo(v -> Example.method1(v));

That code can literally mean 2 completely different things and both are equally valid. The compiler obviously has to end in an error here somehow.

In theory this code:

foo(v -> Example.method1(v < 0 ? "Neg" : "Pos"));

Is no longer ambiguous, but it would be very difficult for the compiler to figure that out. It'd have to essentially try all permutations, realise that all-but-1 end in a compiler error, and then presume that the programmer must know what they are doing and therefore conclude that surely they meant the Integer, String 'version' of what this could mean.

The compiler does not do that and I rather doubt it ever would.

So why does it work in case 3?

And now we finally get to the answer. In case 3 it works because the compiler can 'get there', to an unambiguous answer as to what the lambda must be, without having to go inside-out and outside-in simultaneously (which it will not do).

When the compiler is working on figuring out what:

            .sorted(Comparator.comparing(Map.Entry::getValue))

means, it does not need to worry in any way about trying to disentangle what the signature of that Map.Entry::getValue lambda is meant to be; it can figure it out without knowing this. It knows: Well, sorted is in this case being invoked on a stream of Map.Entry<Integer, Integer> objects (that it can figure out), therefore the only Comparator.comparing call that makes sense here is the one with signature comparing(Function<? super T, ? extends U>), plugging in the known types: comparing(Function<? super Map.Entry<Integer, X extends Comparable<X>>), so it can bring that still quite complicated bunch of types to bear on finally tackling 'how do I parse this lambda' and gets there.

Now we add the .reversed():

            .sorted(Comparator.comparing(Map.Entry::getValue).reversed())

and now this no longer compiles. The outside-in approach brings all the plugged-in generics to bear, but has to then attempt to apply this to the .reversed() method and work backwards from that, which is a bridge too far for the compiler.

In theory some future Java version could be updated to actually (try to) type-analyse so deeply that it would actually figure out. But, if you do that, you get into the territory of a compiler that hangs for years (literally) during the type analysis phase. This is not that hard to do with e.g. the Scala compiler for example. That's bad and it's one of the reasons I somewhat doubt javac will ever try to add the necessary amount of analysis that the situation will ever be different. Separate from the obvious downsides of having a compiler that can take a decade to parse a source file, the extensive Java ecosystem isn't designed for it. IDEs don't, generally, have a 'cancel' button or baked in timeouts.

---

^[1] Due to the rules about method overloading, where it's not allowed if the difference exists solely in the generics, this wouldn't compile. But you can trivially make a copy of java.util.function.Function and now it would compile and is just as ambiguous. Adding this detail seemed unnecessarily complicated to something that is already smacking of rocket science.

Answer 2

The reason the first one doesn't work is because of the Raw Type.

The reason Case 2 works is because you use Map.Entry<Integer,Integer> to set the type reference.

The reason Case 3 Works is because you do not use .reversed(). Without .reversed() The compiler can infer the generic type directly from the context (a longer conversation), but with .reversed() the type inference has to resolve before the reversal which forces the Error in Map.Entry::getValue to the fore front.