Does reduction on an ordered stream reduce in order?

According to the specification it respects the order of the elements.

A proof is very simple. The specification claims that a reduction function has to be associative.

However, associativity it self doesn't make any sense if the order is not preserved. According to the mathematical definition of the associative property:

Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed.

In other words, associative property doesn't imply that:

(a + b) + c = (a + c) + b

It only allows an arbitrary permutation of the order in which operations are applied.

You have asked two questions in one.

1. Does java enforce on an ordered sequential stream (such as the default one from a list) that reduction will always happen according to the encounter order?

Assuming “will always happen” is referring to the order of the function evaluation, the answer is no, this is not guaranteed.

2. Stream.of(" cats ", " eat ", " bats ")
     .reduce("", (a, b) -> a + b); // cats eat bats
   

   With the above, could the output ever be "bats cats eat" or "eat bats cats"? Is that guaranteed somewhere in the spec?

Regardless of the evaluation order of the reduction function (the processing order), the result is guaranteed to be " cats eat bats ", correctly reflecting the encounter order (see also this answer). To ensure that the unspecified processing order still yields the correct result regarding the encounter order, the reduction function must be associative, as specified

Note that the documentation even shows .reduce("", String::concat) as an example of a valid, but inefficient reduction function. Similarly, (a,b) -> b has been acknowledged as a valid way to get the last element of a stream.

The key point is given in the “Associativity” section of the documentation:

Associativity

An operator or function op is associative if the following holds:

(a op b) op c == a op (b op c)

The importance of this to parallel evaluation can be seen if we expand this to four terms:

a op b op c op d == (a op b) op (c op d)

So we can evaluate (a op b) in parallel with (c op d), and then invoke op on the results.

Examples of associative operations include numeric addition, min, and max, and string concatenation.