Monoid
An algebraic concept combining an associative operation and an identity to explain how partial results can be grouped.
· Last updated: 2026-11-07 · 16 min read
Overview
When 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 overall 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 that 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)), allowing 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).1
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.2
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.3
Why use it?
With associativity, the same combining rule works regardless of 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
Start by combining a list of numbers into one value, without an order record. The counts 3, 5, 2, and 7 sum to 17; the amounts sum to 6.60. Familiar addition and zero show where the operation and identity enter the code, before subtraction and floating-point arithmetic demonstrate that a similar-looking combination need not obey the same laws.
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.4
The accumulator in CombineAll starts at T.AdditiveIdentity and changes as each number is added. For the counts it moves from 0 through 3, 8, and 10 to 17; an empty list has nothing to add and leaves the initial 0 unchanged. The generic constraints make addition and its identity available, but do not prove associativity for every value of the type.
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
FalseInteger 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
Suppose we need an overall view of orders received in several batches. Carrying each batch's count, total amount, and maximum together keeps all three figures tied to the same group of orders when another summary is merged in. The goal here is to combine partial summaries into another summary of the same shape instead of passing every original amount on again.
The three statistics could also be aggregated separately. Grouping them here puts three different calculations in one value and makes it easy to observe that combining two summaries returns the same type of summary. Adding counts and sums and selecting the maximum become one operation; we can then check whether an empty summary is neutral and whether regrouping leaves the result unchanged.
OrderStats holds those three parts of a batch summary 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.5
The first summary has count 3, sum 50.75, and maximum 30.25; the second has count 2, sum 46.75, and maximum 41.00. Combining them gives count 5, sum 97.50, and maximum 41.00. The empty third batch leaves those values unchanged. The code groups the combination of all four batches in three ways to compare whether the same inputs produce the same overall summary.
The refunds reveal why 0 is unsuitable as the empty maximum. The maximum of -3.00 and -7.50 is -3.00; inserting a 0 intended to mean "no orders" would corrupt it. Empty therefore uses null to indicate that no maximum exists yet. The later average comparison asks a related question about the summary: keeping a computed average or retaining the count and sum gives different possibilities for combining it correctly.
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
30All 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 , , and 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.
The TypeScript values carry the same three-part batch summary, but 12.50 is written as 1250 integer cents. Its final sum 8700 and maximum 4100 correspond to 87.00 and 41.00 in C#. batch.map(of) turns each amount into a one-order summary, the inner reduce combines a batch, and the outer reduce combines the batch summaries. Both places use combine because its inputs and output all have the same summary type.
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.6An 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
Footnotes
- nLab. monoid. Idea and References sections. The entry cites: Hollings, Christopher. The Early Development of the Algebraic Theory of Semigroups. Archive for History of Exact Sciences 63 (2009) 497-536, doi:10.1007/s00407-009-0044-3. ↩
- Haskell base 4.22.0.0. Data.Monoid. Laws for class Monoid and the descriptions of Sum and Product. ↩
- Haskell base 4.22.0.0. Data.Semigroup. Class Semigroup (since base-4.9.0.0) and the description of Min. ↩
- Microsoft Learn. Generic math. IAdditiveIdentity in the Numeric interfaces table. IAdditiveIdentity.AdditiveIdentity API documentation. ↩
- Microsoft Learn. ParallelEnumerable.Aggregate. Remarks for the overload taking seedFactory and combineAccumulatorsFunc. ↩