Very confused by Java 8 Comparator type inference

Question

I've been looking at the difference between Collections.sort and list.sort, specifically regarding using the Comparator static methods and whether param types are required in the lambda expressions. Before we start, I know I could use method references, e.g. Song::getTitle to overcome my problems, but my query here is not so much something I want to fix but something I want an answer to, i.e. why is the Java compiler handling it in this way.

These are my finding. Suppose we have an ArrayList of type Song, with some songs added, there are 3 standard get methods:

    ArrayList<Song> playlist1 = new ArrayList<Song>();

    //add some new Song objects
    playlist.addSong( new Song("Only Girl (In The World)", 235, "Rhianna") );
    playlist.addSong( new Song("Thinking of Me", 206, "Olly Murs") );
    playlist.addSong( new Song("Raise Your Glass", 202,"P!nk") );

Here is a call to both types of sort method that works, no problem:

Collections.sort(playlist1, 
            Comparator.comparing(p1 -> p1.getTitle()));

playlist1.sort(
            Comparator.comparing(p1 -> p1.getTitle()));

As soon as I start to chain thenComparing, the following happens:

Collections.sort(playlist1,
            Comparator.comparing(p1 -> p1.getTitle())
            .thenComparing(p1 -> p1.getDuration())
            .thenComparing(p1 -> p1.getArtist())
            );
    
playlist1.sort(
        Comparator.comparing(p1 -> p1.getTitle())
        .thenComparing(p1 -> p1.getDuration())
        .thenComparing(p1 -> p1.getArtist())
        );

i.e. syntax errors because it does not know the type of p1 anymore. So to fix this I add the type Song to the first parameter (of comparing):

Collections.sort(playlist1,
            Comparator.comparing((Song p1) -> p1.getTitle())
            .thenComparing(p1 -> p1.getDuration())
            .thenComparing(p1 -> p1.getArtist())
            );
    
playlist1.sort(
        Comparator.comparing((Song p1) -> p1.getTitle())
        .thenComparing(p1 -> p1.getDuration())
        .thenComparing(p1 -> p1.getArtist())
        );

Now here comes the CONFUSING part. For playlist1.sort, i.e. the List, this solve all compilation errors, for both the following thenComparing calls. However, for Collections.sort, it solves it for the first one, but not the last one. I tested added several extra calls to thenComparing and it always shows an error for the last one, unless I put (Song p1) for the parameter.

Now I went on to test this further with creating a TreeSet and with using Objects.compare:

int x = Objects.compare(t1, t2, 
                Comparator.comparing((Song p1) -> p1.getTitle())
                .thenComparing(p1 -> p1.getDuration())
                .thenComparing(p1 -> p1.getArtist())
                );
    
    
    Set<Song> set = new TreeSet<Song>(
            Comparator.comparing((Song p1) -> p1.getTitle())
            .thenComparing(p1 -> p1.getDuration())
            .thenComparing(p1 -> p1.getArtist())
            );

The same thing happens as in, for the TreeSet, there are no compilation errors but for Objects.compare the last call to thenComparing shows an error.

Can anyone please explain why this is happening and also why there is no need to use (Song p1) at all when simply calling the comparing method (without further thenComparing calls).

One other query on the same topic is when I do this to the TreeSet:

Set<Song> set = new TreeSet<Song>(
            Comparator.comparing(p1 -> p1.getTitle())
            .thenComparing(p1 -> p1.getDuration())
            .thenComparing(p1 -> p1.getArtist())
            );

i.e. remove the type Song from the first lambda parameter for the comparing method call, it shows syntax errors under the call to comparing and the first call to thenComparing but not to the final call to thenComparing - almost the opposite of what was happening above! Whereas, for all the other 3 examples i.e. with Objects.compare, List.sort and Collections.sort when I remove that first Song param type it shows syntax errors for all the calls.

Edited to include screenshot of errors I was receiving in Eclipse Kepler SR2, which I have now since found are Eclipse specific because when compiled using the JDK8 java compiler on the command-line it compiles OK.

Answer 1

First, all the examples you say cause errors compile fine with the reference implementation (javac from JDK 8.) They also work fine in IntelliJ, so its quite possible the errors you're seeing are Eclipse-specific.

Your underlying question seems to be: "why does it stop working when I start chaining." The reason is, while lambda expressions and generic method invocations are poly expressions (their type is context-sensitive) when they appear as method parameters, when they appear instead as method receiver expressions, they are not.

When you say

Collections.sort(playlist1, comparing(p1 -> p1.getTitle()));

there is enough type information to solve for both the type argument of comparing() and the argument type p1. The comparing() call gets its target type from the signature of Collections.sort, so it is known comparing() must return a Comparator<Song>, and therefore p1 must be Song.

But when you start chaining:

Collections.sort(playlist1,
                 comparing(p1 -> p1.getTitle())
                     .thenComparing(p1 -> p1.getDuration())
                     .thenComparing(p1 -> p1.getArtist()));

now we've got a problem. We know that the compound expression comparing(...).thenComparing(...) has a target type of Comparator<Song>, but because the receiver expression for the chain, comparing(p -> p.getTitle()), is a generic method call, and we can't infer its type parameters from its other arguments, we're kind of out of luck. Since we don't know the type of this expression, we don't know that it has a thenComparing method, etc.

There are several ways to fix this, all of which involve injecting more type information so that the initial object in the chain can be properly typed. Here they are, in rough order of decreasing desirability and increasing intrusiveness:

• Use an exact method reference (one with no overloads), like Song::getTitle. This then gives enough type information to infer the type variables for the comparing() call, and therefore give it a type, and therefore continue down the chain.
• Use an explicit lambda (as you did in your example).
• Provide a type witness for the comparing() call: Comparator.<Song, String>comparing(...).
• Provide an explicit target type with a cast, by casting the receiver expression to Comparator<Song>.

Answer 2

The problem is type inferencing. Without adding a (Song s) to the first comparison, comparator.comparing doesn't know the type of the input so it defaults to Object.

You can fix this problem 1 of 3 ways:

1. Use the new Java 8 method reference syntax

    Collections.sort(playlist,
               Comparator.comparing(Song::getTitle)
               .thenComparing(Song::getDuration)
               .thenComparing(Song::getArtist)
               );
   

2. Pull out each comparison step into a local reference

     Comparator<Song> byName = (s1, s2) -> s1.getArtist().compareTo(s2.getArtist());
   
     Comparator<Song> byDuration = (s1, s2) -> Integer.compare(s1.getDuration(), s2.getDuration());
   
       Collections.sort(playlist,
               byName
               .thenComparing(byDuration)
               );
   

   EDIT

3. Forcing the type returned by the Comparator (note you need both the input type and the comparison key type)

   sort(
     Comparator.<Song, String>comparing((s) -> s.getTitle())
               .thenComparing(p1 -> p1.getDuration())
               .thenComparing(p1 -> p1.getArtist())
               );
   

I think the "last" thenComparing syntax error is misleading you. It's actually a type problem with the whole chain, it's just the compiler only marking the end of the chain as a syntax error because that's when the final return type doesn't match I guess.

I'm not sure why List is doing a better inferencing job than Collection since it should do the same capture type but apparently not.

Answer 3

Another way to deal with this compile time error:

Cast your first comparing function's variable explicitly and then good to go. I have sort the list of org.bson.Documents object. Please look at sample code

Comparator<Document> comparator = Comparator.comparing((Document hist) -> (String) hist.get("orderLineStatus"), reverseOrder())
                       .thenComparing(hist -> (Date) hist.get("promisedShipDate"))
                       .thenComparing(hist -> (Date) hist.get("lastShipDate"));
list = list.stream().sorted(comparator).collect(Collectors.toList());

Answer 4

playlist1.sort(...) creates a bound of Song for the type variable E, from the declaration of playlist1, which "ripples" to the comparator.

In Collections.sort(...), there is no such bound, and the inference from the type of the first comparator is not enough for the compiler to infer the rest.

I think you would get "correct" behavior from Collections.<Song>sort(...), but don't have a java 8 install to test it out for you.