Folds, traversals, and sequencing

A fold is the abstraction underneath Stream.reduce: walk a collection, accumulate a result. The algebra from Part 12 supplies the vocabulary — a fold that combines with a monoid needs no seed value, and a fold whose combine is associative can be safely regrouped or parallelized.

The Foldable utility

Java cannot express “any foldable structure” without higher-kinded types, so Foldable is honestly a utility class over Iterable/List — the abstractions are real even if the typeclass is not:

1
public final class Foldable {
2

3
    public static <A, B> B foldLeft(Iterable<A> values, B initial, BiFunction<B, A, B> folder) {
4
        B accumulated = initial;
5
        for (A value : values) {
6
            accumulated = folder.apply(accumulated, value);
7
        }
8
        return accumulated;
9
    }
10

11
    public static <A, M> M foldMap(Iterable<A> values, Monoid<M> monoid,
12
                                   Fn1<? super A, ? extends M> mapper) {
13
        M accumulated = monoid.empty();
14
        for (A value : values) {
15
            accumulated = monoid.combine(accumulated, mapper.apply(value));
16
        }
17
        return accumulated;
18
    }
19

20
    public static <T> T combineAll(Iterable<T> values, Monoid<T> monoid) {
21
        return foldMap(values, monoid, Fn1.identity());
22
    }
23
}

foldMap is the workhorse: map each element into a monoidal type, then combine. “Total income across applications” is foldMap(apps, Monoid.longSum(), ApplicationInput::declaredIncome). foldRight (in the repo) walks from the back — the distinction matters for laziness in Part 14.

Traverse and sequence: turning a list of contexts inside out

The scheme engine collects document-verification results: a List<Result<Document, RegistryError>>. What the caller wants is Result<List<Document>, RegistryError> — all the documents, or the first failure:

1
public static <T, E> Result<List<T>, E> sequence(List<Result<T, E>> results) {
2
    List<T> values = new ArrayList<>(results.size());
3
    for (Result<T, E> result : results) {
4
        switch (result) {
5
            case Result.Success<T, E>(var value) -> values.add(value);
6
            case Result.Failure<T, E>(var error) -> {
7
                return Result.failure(error);
8
            }
9
        }
10
    }
11
    return Result.success(values);
12
}

traverse is sequence composed with a per-element function — apply verify(document) to each element, collecting Results as you go. And when “first failure” is wrong — when the citizen should see every invalid document — Validated.sequence accumulates instead:

1
public static <E, T> Validated<E, List<T>> sequence(
2
        List<Validated<E, T>> values, Semigroup<E> semigroup) {
3
    Validated<E, List<T>> accumulated = valid(new ArrayList<>());
4
    for (Validated<E, T> value : values) {
5
        accumulated = map2(accumulated, value, semigroup, (list, element) -> {
6
            list.add(element);
7
            return list;
8
        });
9
    }
10
    return accumulated.map(List::copyOf);
11
}

The choice is the Part 8 rule applied to collections: dependent → Result.sequence stops early; independent → Validated.sequence reports everything. Pick per workflow, not per type.

Compared with the JDK: Stream.collect with a Collector is a fold; Collectors.reducing is foldMap for a monoid you write inline. The jfp versions exist to make the structure visible — foldMap names the monoid explicitly, which is the difference between “an accumulator that happens to work” and “an accumulation you can state laws about.”