Semigroups and monoids

Strip map and flatMap away and something even simpler remains: combining two values of the same type into one. A semigroup is a type with an associative combine — (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). A monoid is a semigroup with an identity element empty such that empty ⊕ a = a = a ⊕ empty. That is the entire definition — and it is the piece Part 8’s Validated.map2 needed to merge error lists without knowing anything about lists.

The interfaces

1
@FunctionalInterface
2
public interface Semigroup<T> {
3

4
    T combine(T left, T right);
5
}

1
public interface Monoid<T> extends Semigroup<T> {
2

3
    T empty();
4

5
    static <T> Monoid<T> of(T empty, Semigroup<T> semigroup) {
6
        return new Monoid<>() {
7
            public T empty() { return empty; }
8
            public T combine(T left, T right) { return semigroup.combine(left, right); }
9
        };
10
    }
11

12
    static Monoid<String> string()          { return of("", (l, r) -> l + r); }
13
    static Monoid<Integer> integerSum()     { return of(0, Integer::sum); }
14
    static Monoid<Boolean> booleanAnd()     { return of(true, Boolean::logicalAnd); }
15
    static <T> Monoid<List<T>> list()       { return of(List.of(), Semigroup.listConcat()); }
16
    // integerProduct, longSum, booleanOr, set() — same shape
17
}

Each factory pairs an identity with an associative combine: 0 for addition, "" for concatenation, List.of() for list concat, Set.of() for union, true for and, false for or.

Where the series already used it

Validated.map2 takes a Semigroup<E> to merge two failures — and NonEmptyList supplies one:

1
public static <T> Semigroup<NonEmptyList<T>> semigroup() {
2
    return NonEmptyList::append;
3
}

Notice what is not there: NonEmptyList has no Monoid instance, because an empty non-empty list does not exist. The type system is telling you the truth about the algebra — a Semigroup is the strongest claim you can lawfully make, so that is the one the library makes.

Scheme example: combining evaluation metrics

Suppose a district-level report folds thousands of eligibility decisions into counters:

1
Monoid<Integer> count = Monoid.integerSum();
2
Integer total = Foldable.combineAll(List.of(1, 1, 0, 1, 1), count); // 4
3

4
Monoid<List<String>> reasons = Monoid.list();
5
List<String> all = reasons.combine(List.of("income"), List.of("residence"));

The monoid’s value is not that a + b is clever — it is that combineAll (built in Part 13) works for any monoid, and the identity element means the empty list case is free: combineAll(List.of(), Monoid.integerSum()) is 0, no special-casing. Associativity additionally licenses parallelism — you may split the input, fold the halves, and combine, which is exactly what Stream.reduce relies on when you give it a combiner.

The laws, tested

1
private static <T> void assertMonoidLaws(Monoid<T> monoid, T a, T b, T c) {
2
    assertThat(monoid.combine(monoid.empty(), a)).isEqualTo(a);
3
    assertThat(monoid.combine(a, monoid.empty())).isEqualTo(a);
4
    assertThat(monoid.combine(monoid.combine(a, b), c))
5
            .isEqualTo(monoid.combine(a, monoid.combine(b, c)));
6
}

Same three-value shape as the monad-law tests: pin the contract on representatives, and promote to property tests if you publish. One subtlety for floating-point types — Double addition is not quite associative ((0.1 + 0.2) + 0.3 ≠ 0.1 + (0.2 + 0.3) at full precision), so “monoid of doubles” is an approximation that matters for financial accumulation. Prefer long paise/cents or BigDecimal, which are exact.