Java Stream `reduce` shenanigans

notes  •  uni  •  java
Cewau  │  Published: 2025-10-29  •  Modified: 2025-11-13

Recall the (simplified) definition of reduce:

T reduce(T id, BinaryOp<T> acc);
U reduce(U id, BiFn<U, T, U> acc, BinaryOp<U> cmb);

This has 2 cases:

  • Sequential execution. This is equivalent to foldl.
  • Parallel execution. Things start to get weird:
    1. The stream is first broken up into multiple substreams, which foldl is applied on individually, each yielding type U (originally type T).
    2. The subresults are then combined, not necessarily via foldl.

The notes then provide a few “conditions” for the triple (id, acc, cmb) — hereafter denoted (, , ):

  1. Purity of A and C. (Obvious)
  2. Identity.
  3. Associativity of .
  4. Compatibility of with .

The motivation of this document is to resolve my own confusion with regard to which conditions are necessary, and which sets of conditions are sufficient — the notes are oddly vague and handwavy on this.

First, definitions:

  • We shall be applying reduce on a stream of elements from a set , which returns a particular output in set .
    • ; ;
    • Notice that the two argument reduce is simply a special case of the three argument version, where and . Thus it shall not be elaborated on.
  • We shall say that a condition is necessary or sufficient for some predicate , where is true if and only if for any stream of elements in , any possible parallel reduction output equals that of the sequential reduction.

We shall initially hold the assumption that repeated application of eventually maps to all values in , that is, , if we define by , and define a sequence by

then we shall assume that

First, consider any . Per our assumption, there exists a stream such that . If we split the stream into 2 substreams and , in either order, we naturally require

Which is our identity condition (1).

Next, we append any element to the stream. If we split it into 2 substreams and , we also require that

which needs to hold , giving rise to our compatibility condition (3).

Finally, consider any ; per our assumption, there exists a stream

such that

We break the stream into 3 substreams , , , which respectively evaluate to , , . Since the order (tree structure) of combination is arbitrary, i.e. Java could opt to apply either of

or

both of which should yield the same result (as per supposition), we arrive at the associativity condition (2).

From here, for any sequentially reduced stream we have

And similarly any other “grouping” of substreams (i.e. parallely reduced) can be broken down into the above form (some of which invoke condition (1)), thus they are equivalent.

Note: The explanation for (0) is obvious and thus omitted.

As mentioned, above hinges upon the assumption that there exists a stream that evaluates to for every . What happens when this is not the case?

Notice that the three (four including (0)) conditions above act primarily on whose domain is . (Aside from (3), but it should be obvious that the tail of the stream can be any element in .)

Suppose as defined above does not evaluate to ; more specifically, it evaluates to some . We will then need to relax the conditions on (the original set becomes sufficient but not necessary):

  1. , for all

Simply attempting to restrict the domain of the universal statement to would not be enough, as may not necessarily be in . We can however perform the same trick:

, define by , and concurrently the sequence by

where represents the subset of “reachable” via repeated applications of on elements in the initial set . We thus restrict the domain of the universal statement in condition 1 to ; as an example, suppose . We can construct the exact “breakdown” of into and choose the two parallelizations that yield, as a generic representation,

with a reminder that every can be expressed as a result of an accumulation of a particular valid substream. Also reminder that .

  1. , for all

Trivial, same reasoning as above. The domain is restricted to .

  1. , for all

Trivial, same reasoning as above. Following the original explanation for (2), we “break” off a stream of s which eventually compute to . The domain is restricted to .

Again, the explanation for (0) is (also) trivial and thus omitted.

TL;DR

The combiner must satisfy

  1. , for all
  2. , for all
  3. , for all

Where is the set of values “reachable” by the reduction.

Update 2025-11-13

Upon closer inspection, I realise that technically, the domain for (3) should use , not , since would never be applied to directly.

I then attempted to find a counterexample where (3) still holds for . After encountering moderate difficulty, I had a further realisation that all three domains can indeed be restricted to , as follows:

Let be any element in .

  1. Since , there exist both a sequence of substreams over and some parallelization (of ) on that sequence which eventually yield .
  2. Since , there does not exist a (full) stream over where sequential application of yields .
  3. Notably, consider the flattened sequence of substreams from [1] into a “full” stream; its sequential application of does not in fact yield (from [2]).

This contradicts either

  • the assumption that (1), (2), and (3) (and trivially (0)) are universally true under ; or
  • if not, then our supposition that there exists an element in .

Hence the updated TL;DR shall be that, the combiner must satisfy

  1. , for all identity
  2. , for all associativity
  3. , for all compatibility

Where is the set of values “reachable” by the accumulation.

And since it wasn’t made directly obvious above (unchanged from previous TL;DR, just included for clarity sake):

  • The associativity of the accumulator doesn’t matter. (It is not really well-defined anyway, for )
  • The above conditions are necessary and sufficient for a parallelization to be “correct”.
  • If the input stream is fixed and predetermined, then effectively reduces to the set of elements in that stream only.
    • Proving properties over this restricted yields sufficiency but of course not necessity.

Additional proof of sufficiency (since necessity is directly implied through ):

Suppose the above conditions are true for all , yet it is still not parallelizable. As proven, there will need to exist some such that one of the conditions are broken.

More specifically by supposition, , or, ; by Mathematical Induction, (since otherwise ).

However, ( and here need not be associative, just implied applied left-to-right)

Thus arriving at a contradiction.