Reduction, match checks and finding elements

Understanding Reduction, match checks and finding elements

A reduction folds a stream into one value by applying a two-argument operator over and over: take something, combine it with the next element, repeat. reduce has three shapes, and the shape you choose is a statement about empty streams and about parallelism. reduce(op) cannot invent an answer for an empty stream, so it returns an Optional; reduce(identity, op) always has identity to fall back on, which is why the operator must satisfy op(identity, x) == x for every x, otherwise the identity leaks into the result as if it were real data. The three-argument form adds a combiner because a parallel run folds chunks separately and then merges them, which is also where the associativity requirement comes from: (a op b) op c must equal a op (b op c), or the answer depends on how the work happened to be split.

anyMatch, allMatch and noneMatch are reductions down to a boolean, and they are permitted to stop early because one element can settle the question. anyMatch quits the moment the predicate is true, allMatch quits the moment it is false, and noneMatch quits on the first true; on an infinite or expensive source that is the difference between an answer and a program that never finishes. Their behaviour on an empty stream follows from logic rather than from a special case: no element satisfies the predicate so anyMatch is false, and there is no counterexample so allMatch and noneMatch are both true, with the predicate never invoked at all.

findFirst and findAny end a pipeline with at most one element, so both hand back an Optional instead of the element itself. findFirst is tied to encounter order: on an ordered stream it must return the element a plain loop with a break would have found, which costs some coordination when the stream is parallel. findAny drops that constraint and may return whichever element a thread has ready first, so it is cheaper but only meaningful when any hit will do. In both cases the Optional is the point: it forces you to write down what happens when nothing matches, which is exactly the branch a hand-written search loop tends to forget.

import java.util.List;
import java.util.Optional;

public class ReduceMatchFind {
    public static void main(String[] args) {
        List<String> words = List.of("kite", "arc", "bramble", "de");

        int totalLength = words.stream()
                .reduce(0, (acc, w) -> acc + w.length(), Integer::sum);
        System.out.println("totalLength = " + totalLength);

        Optional<String> longest = words.stream()
                .reduce((a, b) -> b.length() > a.length() ? b : a);
        System.out.println("longest = " + longest.orElse("none"));

        Optional<String> huge = words.stream()
                .filter(w -> w.length() > 20)
                .reduce((a, b) -> b.length() > a.length() ? b : a);
        System.out.println("huge present = " + huge.isPresent());

        System.out.println("anyMatch(startsWith b) = " + words.stream().anyMatch(w -> w.startsWith("b")));
        System.out.println("allMatch(length >= 2) = " + words.stream().allMatch(w -> w.length() >= 2));
        System.out.println("noneMatch(isEmpty) = " + words.stream().noneMatch(String::isEmpty));
        System.out.println("allMatch on empty stream = " + words.stream().filter(w -> w.length() > 20).allMatch(w -> w.isEmpty()));

        System.out.println("findFirst(length == 3) = " + words.stream()
                .filter(w -> w.length() == 3)
                .findFirst()
                .orElse("none"));
    }
}

Worked examples

import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;

public class ShortCircuit {
    public static void main(String[] args) {
        AtomicInteger tested = new AtomicInteger();

        boolean found = Stream.iterate(1, n -> n + 1)
                .anyMatch(n -> {
                    tested.incrementAndGet();
                    return n % 17 == 0 && n % 5 == 0;
                });

        System.out.println("found = " + found);
        System.out.println("elements tested = " + tested.get());
    }
}

import java.util.List;
import java.util.Optional;

public class FindAndEmptyReduce {
    public static void main(String[] args) {
        List<Integer> nums = List.of(9, 4, 7, 4, 12, 3);

        Optional<Integer> firstEven = nums.parallelStream()
                .filter(n -> n % 2 == 0)
                .findFirst();
        System.out.println("firstEven = " + firstEven.orElse(-1));

        Optional<Integer> product = nums.stream()
                .filter(n -> n > 100)
                .reduce((a, b) -> a * b);
        System.out.println("product of >100 = " + product);
        System.out.println("fallback = " + product.orElse(1));
    }
}

import java.util.Optional;
import java.util.stream.Stream;

public class IdentityMatters {
    public static void main(String[] args) {
        int wrong = Stream.of(-5, -9, -3).reduce(0, Integer::max);
        Optional<Integer> right = Stream.of(-5, -9, -3).reduce(Integer::max);
        int safe = Stream.of(-5, -9, -3).reduce(Integer.MIN_VALUE, Integer::max);

        System.out.println("identity 0 = " + wrong);
        System.out.println("no identity = " + right);
        System.out.println("identity MIN_VALUE = " + safe);
    }
}

Important notes

Common mistakes

Try it yourself