Example of stream reduction with distinct combiner and accumulator

Question

The question is about java.util.stream.Stream.reduce(U identity,BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner) method.

One of the requirements is that the combiner function must be compatible with the accumulator function; for all u and t, the following must hold:

 combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t) (*) 

If the combiner and accumulator are the same, the above equality is automatically true.

A BinaryOperator is actually extending BiFunction, therefore I can use it when BiFunction is required. If U and T are identical, the following is always legal:

operator<T> op = (x,y) -> something;

stream.reduce(id, op, op);

Of course, one cannot always use the combiner as acumulator since, in the general case, they serve for different purposes and are different Java types.

My question

Is there an example of stream reduction with distinct combiner and accumulator?

Also, I'm not interested in trivial examples, but natural examples that I can encounter in practice while doing reduction on parallel streams.

For trivial examples, there are many tutorials, like this one

Why am I asking this question

Basically, the reason this reduction method exists is for parallel streams. It seems to me the condition (*) is so strong that, in practice, it renders this reduction useless since rarely the reduction operations fulfill it.

Answer 1

If the combiner and accumulator are the same? You are confusing things here.

accumulator transforms from X to Y for example (using the identity), while combiner merges two Y into one. Also notice that one is a BiFunction and the other one is a BinaryOperator (which is actually a BiFunction<T, T, T>).

Is there an example of stream reduction with distinct combiner and accumulator?

These look pretty different to me:

    Stream.of("1", "2")
          .reduce(0, (x, y) -> x + y.length(), Integer::sum);

I think you might be confused with things like:

Stream.of("1", "2")
      .reduce("", String::concat, String::concat);

How is it possible to do?

BiFunction<String, String, String> bi = String::concat;

Well there is a hint here.

EDIT

Addressing the part where "different" means different operations, accumulator might sum, while accumulator might multiply. This is exactly what the rule :

combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)

is about, to protected itself from two separate associative functions, but different operations. Let's take an example of two lists (equal, but with different order). This, btw, would be a lot funner with a Set::of from java-9 that adds an internal randomization, so theoretically for the same exact input, you would get different result on the same VM from run to run. But to keep it simple:

List.of("a", "bb", "ccc", "dddd");
List.of("dddd", "a", "bb", "ccc");

And we want to perform:

....stream()
   .parallel()
   .reduce(0,
          (x, y) -> x + y.length(),
          (x, y) -> x * y);

Under the current implementation, this will yield the same result for both lists; but that is an implementation artifact.

There is nothing stopping an internal implementation in saying: "I will split the list to the smallest chunk possible, but not smaller than two elements in each of them". In such a case, this could have been translated to these splits:

["a",    "bb"]     ["ccc", "dddd"]
["dddd", "a" ]     ["bb" , "ccc" ]   

Now, "accumulate" those splits:

0 + "a".length   = 1 ; 1 + "bb".length   = 3 // thus chunk result is 3
0 + "ccc".length = 3 ; 3 + "dddd".length = 7 // thus chunk result is 7 

Now we "combine" these chunks: 3 * 7 = 21.

I am pretty sure you already see that the second list in such a scenario would result in 25; as such different operations in the accumulator and combiner can result in wrong results.

Answer 2

So, here's are a few examples. Some of these may count as "trivial", particularly where there's already a function to do it for you.

An example where T and U are the same

These are quite difficult to come up with, and are a bit contrived, as they generally involve assuming that the elements of stream and the object being accumulated have different meanings, even though they have the same type.

Counting

If we have a stream of integers, we could count them using reduce:

stream.reduce(0, (count, item) -> count+1, (a, b) -> a+b);

Obviously, we could just use stream.count() here, but I'm willing to bet count uses the 3 argument version of reduce internally.

An example where T and U are different

This gives us quite a lot of freedom, and obviously, the accumulator and combiner are never going to be the same here, as they have different types.

One of the most common ways we may want to aggregate is gathering into a collection. We could use reduce for that, but since in Java collection types are typically mutable, using collect will generally be more efficient. This rule applies generally: if the result type mutable, use collect rather than reduce.

Determining the range of a stream of numbers

class Range {
  static Range NONE = new Range(Double.NaN, Double.NaN);

  final double min, max;

  static Range of(double min, double max) {
    if(Double.isNaN(min) || Double.isNaN(max) || min>max) {
      throw new IllegalArgumentException();
    }
    return new Range(min, max);
  }

  private Range(double min, double max) {
    this.min = min;
    this.max = max;
  }

  boolean contains(double value) {
    return this!=Range.NONE && min<=value && max>=value;
  }

  boolean spans(Range other) {
    return this==other
      || other==Range.NONE
      || (contains(other.min) && contains(other.max));
  }

}

Range range = streamOfDoubles.reduce(
    Range.NONE,
    (range, value) -> {
      if(range==Range.NONE)
        return Range.of(value, value);
      else if(range.contains(value))
        return range;
      else
        return Range.of(Math.min(value, range.min), Math.max(value, range.max));
    },
    (a, b) -> {
      if(b.spans(a))
        return b;
      else if(a.spans(b))
        return a;
      else
        return Range.of(Math.min(a.min, b.min), Math.max(a.max, b.max));
    }
);