Monoid

Overview

Suppose orders arrive in batches. Each batch yields a count, a total amount, and a maximum amount, and those partial results are later combined into the full statistics. The environment determines which batch runs first and how the results are grouped.

If grouping changes the total, the same data produces different statistics. Averaging batch averages gives 37.5 for Avg(Avg(10, 20), 60) but 25 for Avg(10, Avg(20, 60)). Choosing 0 as an empty batch's maximum also corrupts the result when combined with a batch containing only negative amounts, such as refunds: the maximum becomes 0.

A monoid consists of a set of values, an operation combining two of them, and an identity. The identity leaves any value unchanged when combined with it, serving as the empty batch and the seed for aggregation. The operation satisfies associativity: Combine(Combine(a, b), c) equals Combine(a, Combine(b, c)). Together, these rules allow partial results to be regrouped without changing the total. Below, the values are OrderStats records, the operation is Combine, and the identity is Empty.

Common monoids include integer addition with 0, integer multiplication with 1, string concatenation with the empty string "", and list concatenation with the empty list. Maximum needs a chosen identity: int.MinValue works for int; otherwise an absent option value can represent "no value yet," expressed here as null in decimal?. A map also forms a monoid with an empty map as identity when the rule for merging values at the same key is associative.

Flow

Combine the partial batch results p0 through p3 from the left, from the right, or in pairs, and the total remains the same. The empty batch p2 equals Empty, so it changes nothing wherever it appears.

History

In abstract algebra, a monoid is a set with an associative binary operation and an identity; it is also called a unital semigroup. The nLab entry's references trace an unrelated earlier use of "monoid" to Arthur Cayley's papers on surfaces in 1863 and 1869. For its modern meaning, the entry cites Hollings (2009, p. 529), who attributes it to Bourbaki's Éléments de Mathématique (1943).¹

Haskell's base library declares the type class as class Semigroup a => Monoid a. Its documentation gives the laws for mempty and <>: right identity, x <> mempty = x; left identity, mempty <> x = x; and associativity, x <> (y <> z) = (x <> y) <> z. It also requires mconcat to equal foldr (<>) mempty, connecting monoids to the fold operation. Because numbers have both additive and multiplicative monoids, base distinguishes them with the wrappers Sum, for addition and 0, and Product, for multiplication and 1.²

The superclass Semigroup has existed since base 4.9.0.0 and requires associativity without an identity. Min, which selects the smaller value, is a Semigroup when comparison through Ord is available. An operation without an identity remains a semigroup; handling empty input requires adding an identity, for instance through an optional value.³

Why use it?

Associativity frees the combining operation from decisions about where the data was split. Results can be combined from the left, in pairs, or after separate threads have accumulated their parts, using the same rule for sequential and parallel aggregation. An identity also defines the result for empty input, reducing separate checks for "no values."

Calling something a monoid does not make its laws hold: the C# type system checks neither associativity nor the identity conditions. The double addition below changes result when regrouped, and decimal also has finite precision, so the actual values and intermediate calculations need attention.

Associativity differs from commutativity. String concatenation tolerates different groupings, but "a" + "b" differs from "b" + "a", so parallel combination must preserve the partial results' order when the monoid is not commutative. The identity must really be neutral too: starting a maximum at 0 gives the wrong answer for all-negative input.

Example

One generic method sums integer and decimal lists. C# has no Monoid interface, but .NET 7 generic math supplies addition through IAdditionOperators<TSelf,TOther,TResult> and an additive identity through IAdditiveIdentity<TSelf,TResult>.AdditiveIdentity. The documentation describes the latter with (x + T.AdditiveIdentity) == x. LINQ Aggregate(seed, func) performs the loop, using that identity as seed so an empty list also returns 0.⁴

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

int[] counts = [3, 5, 2, 7];
decimal[] amounts = [1.10m, 2.20m, 3.30m];
Console.WriteLine(CombineAll(counts));
Console.WriteLine(CombineAll(amounts));
Console.WriteLine(CombineAll(Array.Empty<int>()));

// Regrouping integer addition leaves the result unchanged.
Console.WriteLine((1 + 2) + 3 == 1 + (2 + 3));
// Subtraction changes result when regrouped.
Console.WriteLine($"{(10 - 4) - 3} vs {10 - (4 - 3)}");
// double addition rounds at each step, so regrouping can change its result.
double left = (0.1 + 0.2) + 0.3;
double right = 0.1 + (0.2 + 0.3);
Console.WriteLine($"{left} vs {right}");
// String concatenation is associative but changes result when reordered.
Console.WriteLine(("a" + "b") + "c" == "a" + ("b" + "c"));
Console.WriteLine("a" + "b" == "b" + "a");

// Start from AdditiveIdentity (0 for integers and decimal), then combine with +.
static T CombineAll<T>(IEnumerable<T> values)
    where T : IAdditionOperators<T, T, T>, IAdditiveIdentity<T, T>
    => values.Aggregate(T.AdditiveIdentity, (acc, x) => acc + x);

17
6.60
0
True
3 vs 9
0.6000000000000001 vs 0.6
True
False

Integer addition and string concatenation survive regrouping; subtraction and double addition change result. The final two lines show why an associative operation need not allow reordering.

A broader example

OrderStats groups an order count, sum, and maximum in one record. Combine adds the counts and sums and takes the larger maximum. For an empty set of orders, decimal? uses null for absence, handled by the tuple pattern match (a.Max, b.Max) switch. If each field's operation obeys the monoid laws, their combination obeys them too; the small amounts below illustrate that arrangement. The same partial results are grouped three ways and also combined with PLINQ Aggregate, whose overload accumulates separate partitions and merges them with combineAccumulatorsFunc.⁵

using System;
using System.Collections.Generic;
using System.Linq;

// Four batches of amounts: the third is empty, and the fourth contains refunds only.
decimal[][] batches =
[
    [12.50m, 8.00m, 30.25m],
    [5.75m, 41.00m],
    [],
    [-3.00m, -7.50m],
];

OrderStats[] p = batches.Select(OrderStats.FromBatch).ToArray();
foreach (var s in p) Console.WriteLine($"batch    {s}");

// Regroup the same batch results three ways.
var leftFirst = p.Aggregate(OrderStats.Empty, OrderStats.Combine);
var rightFirst = OrderStats.Combine(p[0], OrderStats.Combine(p[1], OrderStats.Combine(p[2], p[3])));
var pairwise = OrderStats.Combine(OrderStats.Combine(p[0], p[1]), OrderStats.Combine(p[2], p[3]));
// PLINQ accumulates orders in partitions, then merges their results with Combine.
var parallel = batches.SelectMany(b => b).AsParallel().Aggregate(
    () => OrderStats.Empty,
    (acc, amount) => OrderStats.Combine(acc, OrderStats.Of(amount)),
    OrderStats.Combine,
    s => s);
Console.WriteLine($"left     {leftFirst}");
Console.WriteLine($"right    {rightFirst}");
Console.WriteLine($"pairwise {pairwise}");
Console.WriteLine($"parallel {parallel}");
Console.WriteLine(leftFirst == rightFirst && rightFirst == pairwise && pairwise == parallel);

// A non-neutral seed: Max = 0 changes the maximum of an all-refund batch to 0.
var notNeutral = new OrderStats(0, 0m, 0m);
Console.WriteLine($"empty    {OrderStats.Combine(OrderStats.Empty, p[3])}");
Console.WriteLine($"wrong    {OrderStats.Combine(notNeutral, p[3])}");

// Averaging averages is not associative.
static decimal Avg(decimal a, decimal b) => (a + b) / 2;
Console.WriteLine($"{Avg(Avg(10m, 20m), 60m)} vs {Avg(10m, Avg(20m, 60m))}");
// Keep count and sum, then compute the average once at the end.
var three = new[] { 10m, 20m, 60m }.Aggregate(OrderStats.Empty, (acc, x) => OrderStats.Combine(acc, OrderStats.Of(x)));
Console.WriteLine(three.Sum / three.Count);

record OrderStats(int Count, decimal Sum, decimal? Max)
{
    // Identity: combining it changes nothing. No orders means no maximum (null).
    public static readonly OrderStats Empty = new(0, 0m, null);

    public static OrderStats Of(decimal amount) => new(1, amount, amount);

    public static OrderStats FromBatch(decimal[] batch) =>
        batch.Aggregate(Empty, (acc, x) => Combine(acc, Of(x)));

    // Associative combination adds counts and sums and chooses the larger maximum.
    public static OrderStats Combine(OrderStats a, OrderStats b) =>
        new(a.Count + b.Count, a.Sum + b.Sum, (a.Max, b.Max) switch
        {
            (null, _) => b.Max,
            (_, null) => a.Max,
            _ => Math.Max(a.Max.Value, b.Max.Value),
        });

    public override string ToString() => $"count={Count}, sum={Sum}, max={Max?.ToString() ?? "none"}";
}

batch    count=3, sum=50.75, max=30.25
batch    count=2, sum=46.75, max=41.00
batch    count=0, sum=0, max=none
batch    count=2, sum=-10.50, max=-3.00
left     count=7, sum=87.00, max=41.00
right    count=7, sum=87.00, max=41.00
pairwise count=7, sum=87.00, max=41.00
parallel count=7, sum=87.00, max=41.00
True
empty    count=2, sum=-10.50, max=-3.00
wrong    count=2, sum=-10.50, max=0
37.5 vs 25
30

All four approaches give count=7, sum=87.00, max=41.00. Every intermediate sum for these inputs is represented exactly, so regrouping and reordering with Combine leaves the result unchanged, but using decimal does not guarantee associativity for all amounts. Adding 10^28, -10^28, and 0.01 from the left gives 0.01; grouping the last two first gives 0 because of rounding, without overflowing. The PLINQ Aggregate documentation's Remarks do not specify the partition merge order, so parallel aggregation needs operations that are associative and commutative for the actual inputs. Compute an average once from the accumulated count and sum instead of averaging averages, keeping the intermediate counts and sums within a range where they are represented exactly. This example has no decimal overflow checks or distinction between currencies.

TypeScript example

TypeScript defines the identity empty and combining function combine explicitly, using array reduce and reduceRight to fold. Because number is double, amounts are stored as integer cents to avoid grouping-dependent fractional sums.

type OrderStats = { readonly count: number; readonly sum: number; readonly max: number | null };

// Identity: no orders gives zero count and sum and no maximum.
const empty: OrderStats = { count: 0, sum: 0, max: null };

function of(cents: number): OrderStats {
  return { count: 1, sum: cents, max: cents };
}

// Associative combination adds counts and sums and chooses the larger maximum.
function combine(a: OrderStats, b: OrderStats): OrderStats {
  const max = a.max === null ? b.max : b.max === null ? a.max : Math.max(a.max, b.max);
  return { count: a.count + b.count, sum: a.sum + b.sum, max };
}

function show(s: OrderStats): string {
  return `count=${s.count}, sum=${s.sum}, max=${s.max ?? "none"}`;
}

// Store integer cents; adding fractional number (double) amounts can break associativity.
const batches: number[][] = [[1250, 800, 3025], [575, 4100], [], [-300, -750]];
const p = batches.map((batch) => batch.map(of).reduce(combine, empty));

const leftFirst = p.reduce(combine, empty);
const rightFirst = p.reduceRight((acc, s) => combine(s, acc), empty);
const pairwise = combine(combine(p[0], p[1]), combine(p[2], p[3]));
console.log("left     " + show(leftFirst));
console.log("right    " + show(rightFirst));
console.log("pairwise " + show(pairwise));
console.log(show(leftFirst) === show(rightFirst) && show(rightFirst) === show(pairwise));

// The identity defines an empty-list result. Seedless reduce throws TypeError.
const none: OrderStats[] = [];
console.log("empty    " + show(none.reduce(combine, empty)));
try {
  none.reduce(combine);
} catch (e) {
  console.log(e instanceof TypeError ? "TypeError: " + e.message : "unexpected");
}

console.log((0.1 + 0.2) + 0.3, 0.1 + (0.2 + 0.3));

left     count=7, sum=8700, max=4100
right    count=7, sum=8700, max=4100
pairwise count=7, sum=8700, max=4100
true
empty    count=0, sum=0, max=none
TypeError: Reduce of empty array with no initial value
0.6000000000000001 0.6

An identity seed defines the result even for an empty list; without a seed, reduce throws TypeError on an empty array. Integer-cent sums are exact only within Number.MAX_SAFE_INTEGER, a boundary this example does not check.

See also

• Fold

• Option Type

• Functional Programming

• Programming Patterns

Example environment: each C# example is a separate .NET 10 console program; compile TypeScript for ES2022 or later, then run the JavaScript with Node.js.