Why does adding ".map(a -> a)" allow this to compile?

Question

This is related to my answer to "stream reduction incompatible types". I don't know why what I suggested works, and Holger rightly pressed me on this. But even he doesn't seem to have a clear explanation for why it works. So, let's ask it as its own question:

The following code does not compile in javac (for the links to ideone below, this is sun-jdk-1.8.0_51, per http://ideone.com/faq):

public <T> Object with(Stream<Predicate<? super T>> predicates) {
  return predicates.reduce(Predicate::or);
}

And rightly so: or-ing together two predicates from this stream is like writing:

Predicate<? super T> a = null;
Predicate<? super T> b = null;
a.or(b);  // Compiler error!

However, it does compile in intellij, although with a raw type warning on the Predicate::or method reference. Apparently, it would also compile in eclipse (according to the original question).

But this code does:

public <T> Object with(Stream<Predicate<? super T>> predicates) {
  return predicates.map(a -> a).reduce(Predicate::or);
                // ^----------^ Added
}

Ideone demo

Despite the fact I thought to try this, it's not exactly clear to me why this would work. My hand-wavy explanation is that .map(a -> a) acts like a "cast", and gives the type inference algorithm a bit more flexibility to pick a type which allows the reduce to be applied. But I'm not sure exactly what that type is.

Note that this isn't equivalent to using .map(Function.identity()), because that is constrained to return the input type. ideone demo

Can anybody explain why this works with reference to the language spec, or if, as suggested by Holger, it is a compiler bug?

---

A bit more detail:

The return type of the method can be made a bit more specific; I omitted it above so that the nasty generics on the return type wouldn't get in the way:

public <T> Optional<? extends Predicate<? super T>> with(
    Stream<Predicate<? super T>> predicates) {
  return predicates.map(a -> a).reduce(Predicate::or);
}

This is the output of compiling with -XDverboseResolution=all. Not entirely sure if this is the most relevant output I can post to debug the type inference; please advise if there is something better:

Interesting.java:5: Note: resolving method <init> in type Object to candidate 0
class Interesting {
^
  phase: BASIC
  with actuals: no arguments
  with type-args: no arguments
  candidates:
      #0 applicable method found: Object()

Interesting.java:7: Note: resolving method map in type Stream to candidate 0
    return predicates.map(a -> a).reduce(Predicate::or);
                     ^
  phase: BASIC
  with actuals: <none>
  with type-args: no arguments
  candidates:
      #0 applicable method found: <R>map(Function<? super T#1,? extends R>)
        (partially instantiated to: (Function<? super Predicate<? super T#2>,? extends Object>)Stream<Object>)
  where R,T#1,T#2 are type-variables:
    R extends Object declared in method <R>map(Function<? super T#1,? extends R>)
    T#1 extends Object declared in interface Stream
    T#2 extends Object declared in method <T#2>with(Stream<Predicate<? super T#2>>)

Interesting.java:7: Note: Deferred instantiation of method <R>map(Function<? super T#1,? extends R>)
    return predicates.map(a -> a).reduce(Predicate::or);
                         ^
  instantiated signature: (Function<? super Predicate<? super T#2>,? extends Predicate<CAP#1>>)Stream<Predicate<CAP#1>>
  target-type: <none>
  where R,T#1,T#2 are type-variables:
    R extends Object declared in method <R>map(Function<? super T#1,? extends R>)
    T#1 extends Object declared in interface Stream
    T#2 extends Object declared in method <T#2>with(Stream<Predicate<? super T#2>>)
  where CAP#1 is a fresh type-variable:
    CAP#1 extends Object super: T#2 from capture of ? super T#2

Interesting.java:7: Note: resolving method reduce in type Stream to candidate 1
    return predicates.map(a -> a).reduce(Predicate::or);
                                 ^
  phase: BASIC
  with actuals: <none>
  with type-args: no arguments
  candidates:
      #0 not applicable method found: <U>reduce(U,BiFunction<U,? super T,U>,BinaryOperator<U>)
        (cannot infer type-variable(s) U
          (actual and formal argument lists differ in length))
      #1 applicable method found: reduce(BinaryOperator<T>)
      #2 not applicable method found: reduce(T,BinaryOperator<T>)
        (actual and formal argument lists differ in length)
  where U,T are type-variables:
    U extends Object declared in method <U>reduce(U,BiFunction<U,? super T,U>,BinaryOperator<U>)
    T extends Object declared in interface Stream

Interesting.java:7: Note: resolving method metafactory in type LambdaMetafactory to candidate 0
    return predicates.map(a -> a).reduce(Predicate::or);
                          ^
  phase: BASIC
  with actuals: Lookup,String,MethodType,MethodType,MethodHandle,MethodType
  with type-args: no arguments
  candidates:
      #0 applicable method found: metafactory(Lookup,String,MethodType,MethodType,MethodHandle,MethodType)

Interesting.java:7: Note: resolving method metafactory in type LambdaMetafactory to candidate 0
    return predicates.map(a -> a).reduce(Predicate::or);
                                         ^
  phase: BASIC
  with actuals: Lookup,String,MethodType,MethodType,MethodHandle,MethodType
  with type-args: no arguments
  candidates:
      #0 applicable method found: metafactory(Lookup,String,MethodType,MethodType,MethodHandle,MethodType)

Yuki

Andy, what about map(Function.identity())? Have tried that one? Did it work? – Circumfluent

@FedericoPeraltaSchaffner yes, and it doesn't compile. – Yuki

Andy, original code, in IntelliJ it doesn't compile. What happens is that it's not marked as an error (no red underline). So this is a bug in IntelliJ. – Circumfluent

I don't like my answer very much and will probably delete it soon, but I want to point out that the version without map is not the same as the plain a.or(b), since those type parameters are actually different captures, but the entries in the stream do have the same type (the same capture), you just can't really express that in plain code. – Gudgeon

@JornVernee the compilation errors look remarkably similar: both say incompatible types: Predicate<CAP#1> cannot be converted to Predicate<? super CAP#2>. Method reference version; a.or(b) version – Yuki

Stumbled across this lambda that seems to have worked: Function<Predicate, Predicate<T>> predicatePredicateFunction = a -> a;. Perhaps this is what's being inferred? – Squeegee

@JoeC that's got a raw type in it, though, and there are no raw type warnings when I compile. – Yuki

One thing to note is that map(t -> t) causes the introduction of a new type variable CAP#1 while map(Function.identity()) does not, it will use ? super T#2 instead, which looks inconsistent to me, as both are poly expressions. But both should end up in identical constraints anyway. The most interesting aspect is that the verbose output doesn’t show any resolution for Predicate::or, it looks like the compiler just didn’t care. – Inn

@Inn yes; I think the key thing is that the output type of the map is Stream<Predicate<CAP#1>> - am I right in thinking that this is logically the same as Stream<Predicate<Q>>, for some type variable Q? If it is, that's why it's possible then to apply reduce(Predicate::or). But the dropping of the lower bound feels... odd. – Yuki

The first version does indeed compile and run in Eclipse (Neon.3 Release (4.6.3)) – Iorio

@Iorio thanks for verifying. – Yuki

@Andy Turner: the lower bound hasn’t dropped, but ? super T#2 has been captured in CAP#1. I could consider that a reasonable behavior if javac wasn’t denying the same for every other generic construct. It’s just inconsistent not to allow ? super Type to be captured by an explicitly declared type variable, e.g. when invoking a method, but allow it for the compiler generated type variable. – Inn

@Inn Right, sorry - as per usual, you are correcting me on sloppy terminology. That's what I meant; and I agree with your objection to the inconsistency. The question remains whether this is explicitly allowed by the spec or not. – Yuki

Even with javac, the assignment Predicate<? super T> a = null; Predicate<? super T> b = a; (similarly with extends) compiles, but the invocation a.or(b); does not. Intuitively, If the first compiles the second should as well. And in similar cases, it does compile: ideone.com/wVlROT. The longer I look at this, the more I think this is an type system limitation. – Gudgeon

Two questions come to mind and my terminology is going to be wrong. First you made the statement it doesn't compile in javac, the question is which javac? The second question is a curiosity about the boundaries of the type erasure problem. By invoking the map method with a lamda function you have created an anonymous forkjointask, so wouldn't this additional step allow the compiler the flexibility to map the types appropriately without the erasure voodoo? – Bristow

@MichaelH I've edited the javac version into the question. With regard to the second point, there is no ForkJoinTask (it's not a parallel stream), but even if there were, that's just an implementation detail which has nothing to do with the type inference. – Yuki

@AndyTurner fair points, I was trying to wrap my head around it as I'm starting to dig deeper into java. One thing that does pop out in the debug statement is there is no reduce method which accepts the explicit stream of Predicates, however the map function creates and returns a new stream where some level of type coercion could be taking place to satisfy the reduce method parameters. – Bristow

Thanks for your time! – Reichenberg

I noticed that reduce() accepts a BinaryOperator (which extends BiFunction<T,T,T>), i.e. input and output types must be equal. However Predicate.or() has different input and output types. It may hint to a bug in cases where this acutally compiles. – Laurasia

Answer 1

Unless I am missing something in how FunctionalInterface inferences occur, it seems pretty obvious that you can't call reduce on a Stream < ? super Predicate > because it does not have sufficient typing to be inferred as a BinaryOperator.

The method reference hides a very important part of the story, the second parameter.

return predicates.map(a->a).reduce((predicate, other) -> predicate.or(other));

If you remove the call to map, the compiler does not have the opportunity to type the stream appropriately to satisfy the second capture requirements. With map the compiler is given the latitude to determine the types required to satisfy the captures, but without a concrete binding of the generics the two captures can only be satisfied with a Stream of Object which is likely what would result through map().

The Predicate interface as implemented now is simply building a chain, but the use is expected to be a composed entity. It is assumed to take a single parameter, but in fact the nature of AND and OR require two parameters without a type guarantee because of the shortcomings of Java's generics. In this way the API seems to be less than ideally designed.

The call to map() cedes the control of the typing, from the explicit Stream of Predicates, to one the compiler can guarantee will satisfy all captures.

The following both satisfy the compiler in IDEone, by directly inducing a flexible enough type in the case of Object, or a known type in the case of T.

public <T> Optional<? extends Predicate<? super T>> with(Stream<Predicate<Object>> predicates)
public <T> Optional<? extends Predicate<? super T>> with(Stream<Predicate<T>> predicates)

Java generics still need a way to force capture type equivalence, as the helper methods are clearly not enough.

Bristow