collect & Mutable Reduction

## The problem mutable reduction solves A **stream** in Java is a pipeline that processes a sequence of elements (e.g. `list.stream()`). A **terminal operation** ends the pipeline and produces a result. **Reduction** means combining all the elements into a single result. There are two flavors of reduction: 1. **Immutable (functional) reduction** — `reduce()`. Each step takes the running result and the next element and returns a *brand-new* result value, never modifying anything. Great for `int` sums, `max`, string-of-numbers, etc., where the result is small and cheap to copy. 2. **Mutable reduction** — `collect()`. Instead of producing a new result each step, you keep **one mutable container** and *mutate it in place*, adding each element to it. Why does mutable reduction exist? Consider building a `List` of a million elements with `reduce`. Each step would have to create a new list containing all previous elements plus one more — copying the whole list every time. That is O(n²) and allocates a million lists. Mutable reduction instead creates **one** `ArrayList` and calls `add()` a million times — O(n), one container. ## The three (well, four) functions `collect` is defined by three pieces of behavior: - **supplier** — `Supplier<R>`: creates a new, empty result container. Example: `ArrayList::new`. - **accumulator** — `BiConsumer<R, T>`: folds one element `T` into the container `R` by **side effect** (it returns nothing; it mutates). Example: `List::add`. - **combiner** — `BiConsumer<R, R>`: merges the contents of a second partial container into the first. Example: `List::addAll`. This is only used when the stream is split for **parallel** execution — each worker thread builds its own partial container, and the combiner stitches them together. The low-level three-arg form exposes these directly: ```java List<String> result = stream.collect( ArrayList::new, // supplier ArrayList::add, // accumulator ArrayList::addAll // combiner ); ``` A **Collector** (the one-arg form `collect(Collector)`) bundles those three functions *plus* a fourth, the **finisher** (`Function<A,R>`), which transforms the mutable accumulation type `A` into the final result type `R` (often identity — no transform). `Collectors.toList()`, `Collectors.toMap(...)`, `Collectors.joining()` are all pre-built Collectors. ## Sequential vs parallel - **Sequential:** the supplier is called once, the accumulator runs for every element, the combiner is *never* called. - **Parallel:** the stream is split into chunks; each chunk gets its own container from the supplier and is accumulated independently, then partial containers are merged pairwise by the combiner. The container can be **reused/merged** rather than recreated, which is the whole performance point. ## Correctness contract For `collect` to give a correct, parallel-safe answer, the supplier/accumulator/combiner must form an **associative** and **non-interfering** reduction: the combiner of two accumulations must equal accumulating both into one. If `accumulator` and `combiner` disagree (e.g. one sorts and the other doesn't), parallel results become wrong or nondeterministic. ## Bottom line Use `collect` (mutable reduction) when your result is a *container*; use `reduce` (immutable reduction) when your result is a single *value* and combining is cheap and side-effect-free.