Why doesn't Stream#reduce implicitly accept an accumulative function handling super type elements?

Question

Considering these classes and accumulation function, which represent a simplification of my original context (yet reproducing the same problem):

abstract static class Foo {
    abstract int getK();
}
static class Bar extends Foo {
    int k;
    Bar(int k) { this.k = k; }
    int getK() { return this.k; }
}

private static Foo combined(Foo a1, Foo a2) {
    return new Bar(a1.getK() + a2.getK());
}

I have attempted to perform an accumulation of items (originally data indexing reports) by relying on a separate function, combined, which deals directly with elements of type Foo.

Foo outcome = Stream.of(1,2,3,4,5)
        .map(Bar::new)
        .reduce((a,b) -> combined(a, b))
        .get();

It turns out that this code results in a compilation error (OpenJDK "1.8.0_92"): "Bad return type in lambda expression: Foo cannot be converted to Bar". The compiler insists on attempting to reduce the stream using Bar as the accumulative element, even when there is Foo as a common type for both the arguments to the cumulative function and its return type.

I also find peculiar that I can still take this approach as long as I explicitly map the stream into a stream of Foos:

Foo outcome = Stream.of(1,2,3,4,5)
        .<Foo>map(Bar::new)
        .reduce((a,b) -> combined(a, b))
        .get();

Is this a limitation of Java 8's generic type inference, a small issue with this particular overload of Stream#reduce, or an intentional behaviour that is backed by the Java specification? I have read a few other questions on SO where type inference has "failed", but this particular case is still a bit hard for me to grasp.

Answer 1

The problem is that you're definitely creating a BinaryOperator<Foo> - you have to be, as you're returning a Foo. If you change combined() to be declared to return Bar (while still accepting Foo) then you'd be fine. It's the fact that the return type is tied to the input type that's the problem - it can't be either covariant or contravariant, because it's used for input and output.

To put it another way - you're expecting reduce((a, b) -> combined(a, b)) to return an Optional<Foo>, right? So that suggests that you're expecting the T of the reduce() call to be Foo - which means that it should be operating on a Stream<Foo>. A Stream<Bar> only has a single-parameter reduce method that takes a BinaryOperator<Bar>, and your lambda expression using combined simple isn't a BinaryOperator<Bar>.

Another alternative is to add a cast to the lambda expression:

Foo outcome = Stream.of(1,2,3,4,5)
    .map(Bar::new)                
    .reduce((a,b) -> (Bar)combined(a, b))
    .get();

Answer 2

I think this is related to the reason why a list of Derived is not a list of Base. By doing .map(Bar::new) you create a stream of Bar. It is obviously not trivially convertible to stream of Foo according to the general rule “If B is an A, then X<B> is not X<A>”.

Then you're trying to reduce it, but reduce must create a stream of exactly the same type. What you want is reduce behaving like both reduce and map in the sense that you want it both reduce the stream to a single instance and change its type. This is more like a job for collect (except that collect works with mutable types).

But there is a variant of reduce that can change the type. And its signature actually gives us a hint of why the simple overload can't change the type of the stream:

<U> U reduce(U identity,
             BiFunction<U,? super T,U> accumulator,
             BinaryOperator<U> combiner)

It takes two functions! Why? Because Java streams are parallelizible. So a stream can perform reduction by parts and then combine parts into a single value. Here it is possible because we give an additional combiner. In your case one function is supposed to act as both accumulator and combiner which creates all the confusion about what exactly is its signature.

So the reason it doesn't work is because that overload lacks combiner that could combine partial results. Of course it isn't a “hard” reason in the sense that since Foo is a superclass of Bar, it is technically possible to use the same thing as both accumulator and combiner, like you do in your example with explicit <Foo>.

So it looks like a design decision that is intended to avoid possible confusion because of a stream randomly changing types after reduction. If you really want it, there is that another overload, but its signature is ugly enough to make the type change obvious just from looking at the code.

Answer 3

Update

The simple answer to your question is that your reduce takes a BinaryOperator<Bar>, which says you must pass in a function that takes in two Bar values and returns a Bar. Your lambda accepts two Bar parameters just fine, because your combined function sees that Bar is assignable to Foo. For the return type however, the thinking goes in the opposite direction; while for the parameters you are concerned that the values passed in match your function, for the return type, you have to worry about whether the caller of your function can accept the type your function returns. Because your function returns Foo, and the receiver is expecting a Bar, there is a compiler error, for the same reason that this fails:

Bar b = new Foo(1);

Adding the cast works, but it is unsafe, for the same reason that

Bar b  = (Bar) new Foo(1);

works but isn't safe -- not every instance of Foo will necessarily be a Bar.

There is a safe way to do the reduction, without casts, using the 3-parameter reduce. It lets you reduce to a different type than the stream type.

Foo combined = Stream.of(1,2,3,4,5)
            .map(Bar::new)
            .reduce(
                new Bar(0),                       // starting value, type Foo
                (Foo a, Bar b) -> combined(a, b), // apply each Bar to create new Foo 
                (Foo a, Foo b) -> combined(a,b)); // combine intermediate results if parallel

The first parameter, (Foo)new Bar(0) is the initial value to seed the reduction, and will be the value returned if the stream is empty.

The second parameter folds in each Bar from the Stream into a new accumulated Foo value.

The third parameter, used chiefly in parallel streams, combines two intermediate accumulated Foo values.

The combine function works for both the accumulator and combiner only because Bar happens to be assignable to Foo.

Note that, as was mentioned in the comments, this can be written more succinctly because, in this case, the Stream element type is assignable to the Accumulator type, so it can be simplified to

Foo combined = Stream.of(1,2,3,4,5)
            .map(Bar::new)
            .reduce(new Bar(0), (a,b) -> combined(a, b), (a, b) -> combined(a,b));

Or

Foo combined = Stream.of(1,2,3,4,5)
            .map(Bar::new)
            .reduce(new Bar(0), MyClass::combined, MyClass::combined);

Answer 4

You are indeed hitting a limitation of Java 8’s type inference. In one sentence, target typing doesn’t work for the receiver of a method invocation. So in your code, you have an invocation of the method reduce on the result of Stream.of(1,2,3,4,5).map(Bar::new), which makes that expression the receiver of the method invocation .reduce((a,b) -> combined(a, b)) which can’t use any information about what reduce might expect.

Instead, the type of the expression Stream.of(1,2,3,4,5), which is the receiver of the .map invocation, and the argument Bar::new are the only information to determine the type of the resulting Stream and there is nothing suggesting that Stream<Foo> could be the better choice compared with Stream<Bar>.

It’s the same issue as described in this answer and that answer.

It can be easily demonstrated how it would work, if type inference was possible, by dissolving the method invocations:

Stream<Foo> s= Stream.of(1,2,3,4,5).map(Bar::new);
Foo outcome = s.reduce((a,b) -> combined(a, b)).get();

which works smoothly.

Besides providing an explicit type for map as with .<Foo>map(Bar::new), there’s also the alternative

Optional<Foo> outcome =
    Stream.of(1,2,3,4,5)
    .map(Bar::new)
    .collect(Collectors.reducing((a,b) -> combined(a, b)));

This works because collect on a Stream<T> allows an argument of type Collector<? super T,…> so the compiler can infer Collector<Foo,…> from the expected target type which is valid for invoking collect on a Stream<Bar>. However, you can’t chain a get() call to get the Foo immediately, for the same reason described above; the target type won’t be supplied to the receiver of the method invocation.