What correctness laws must identity, accumulator, and combiner satisfy for reduce to give correct (and parallel-safe) results?

## Setting the stage `Stream.reduce` performs a **reduction** (a *fold*): it collapses a stream into one value by repeatedly applying a two-argument **accumulator** function, seeded by an **identity** value, and (in the three-arg form) merging partial results with a **combiner**. The crucial fact is that the stream framework gives **no guarantee about how it groups or orders the combining** — particularly under **parallel** execution, where the data is split into chunks processed on different threads and merged. For the answer to be correct and deterministic regardless of how it splits, three algebraic laws must hold. (These are exactly the properties of a *monoid* in math, but you don't need that word to apply them.) ## Law 1 — Identity is a neutral element For all `x`: `combiner.apply(identity, x) == x` (and `accumulator.apply(identity, x) == x`). The identity is the value that "does nothing" when combined. For addition it's `0` (`0 + x == x`); for multiplication `1`; for string concatenation the empty string `""`; for max it's the smallest possible value. **Why it matters:** when the framework splits a stream into N chunks, each chunk's reduction starts from `identity`, so the identity is effectively folded in N times. If the identity isn't neutral, each extra split corrupts the result. Classic bug: using `1` as the identity for a sum — `stream.reduce(1, Integer::sum)` over `[1,2,3]` gives `7` sequentially but can give `8`, `9`, … in parallel as more identities are injected. ## Law 2 — The accumulator must be associative For all `a, b, c`: `op(op(a, b), c) == op(a, op(b, c))`. Associativity means the **grouping** of operations doesn't change the result. Reduce explicitly does **not** promise left-to-right evaluation; it may compute `((a op b) op c)` or `(a op (b op c))` or, in parallel, `(a op b) op (c op d)`. So the op must be associative. **Addition, multiplication, max, min, string concatenation are associative.** **Subtraction and division are not:** `(10 - 1) - 2 = 7` but `10 - (1 - 2) = 11`. Using subtraction in reduce gives one answer sequentially and a different one in parallel — a silent correctness bug. (Note: associativity is *not* the same as commutativity. Reduce requires associativity; it does *not* require commutativity, because it preserves encounter order — string concatenation is associative but not commutative, and reduce keeps the strings in order.) ## Law 3 — Combiner must be consistent with the accumulator For all `u` (a partial result of type U) and `t` (an element of type T): `combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)`. In the three-arg form the accumulator folds an element into a partial result, while the combiner merges two partial results. They must agree: merging a partial result `u` with the partial result built from a single element `t` must equal folding `t` directly into `u`. If they disagree, sequential and parallel runs diverge. Typically the combiner is just the accumulator restricted to two U values (e.g. accumulator and combiner are both `Integer::sum`), which makes consistency automatic. ## How violations show up The insidious part: a broken law often **passes every sequential test** because sequential reduction happens to use one fixed grouping/order and injects the identity only once. The bug surfaces only when someone calls `.parallel()` — or when the JDK changes its splitting heuristics. So you reason about these laws *statically* rather than relying on tests. Rule of thumb: pick a true neutral identity, use an associative op, and keep the combiner identical in spirit to the accumulator. ## Checklist - Is `combine(identity, x) == x` for all x? (neutral identity) - Does grouping not matter — is the op associative? (avoid `-`, `/`) - Does the combiner agree with the accumulator on a single element? If yes to all three, the reduction is parallel-safe.