Abstract Algebra in Action: Semigroups and Monoids in C#

Many production problems are aggregation problems in disguise: merge partial results, combine filters, reduce collections, or compute values in parallel. Abstract algebra gives those operations precise names and laws, which makes it easier to design reusable code and reason about whether regrouping or parallel execution is safe.

This article introduces semigroups and monoids through C# examples. The point is not to decorate ordinary code with mathematical vocabulary; it is to make composition rules explicit enough that the compiler and your teammates can see them.

---

Many of us studied at technical universities and took a long list of mathematics courses while wondering why we needed them. Algebra may have been one of those courses. I do not mean a school textbook packed with tedious exercises about polynomials and equations. Abstract algebra is a difficult, expansive subject with a steep learning curve, but it is also fascinating. Its central objects of study are algebraic structures, which you can build almost anywhere and from almost anything. They can also inspire new approaches to writing code. Before we get there, let us take a short algebraic detour.

Semigroups, Monoids, and Their Laws

We will barely scratch the surface of abstract algebra. We will cover only the basic axioms and definitions needed to understand what is going on. There will not even be any theorems or proofs.

Let us begin with an arbitrary set $X$ , assuming familiarity with sets and mappings. If we take a mapping $\circ : X \times X \to X$ together with our set, we get an algebraic structure. In other words, an algebraic structure is a pair $(X, \circ)$ consisting of a set and a closed binary operation. The integers under addition, $(\mathbb{Z} , +)$ , are one example.

This is where the operations become important: they determine the structure and behavior of the elements. Arbitrary functions are not useful enough, so we require them to have certain properties. Put differently, the operation must satisfy a set of axioms. We will add them one at a time.

Associativity is a natural first constraint. A binary operation $\circ$ on a set $X$ is associative if the following holds:

$$(a \circ b) \circ c = a \circ (b \circ c)$$

Once this axiom holds, $(X, \circ)$ is a semigroup. Why are semigroups useful? Associativity means that grouping does not affect the result of the operation, so semigroup elements can be "combined" in parallel. We would also like to be able to ignore some elements. That takes us to the next level of structure.

An element $e \in X$ is called an identity element if the following holds:

$$\exists \; e \in X : \forall x \in X \; e \circ x = x \circ e = x$$

Our semigroup $(X, \circ)$ with identity $e$ is now a monoid. The two equalities in the axiom are not redundant: left and right identities also exist, but that is a different story.

Which monoids do we already know? Once again, the integers: $(\mathbb{Z}, +,0)$ , $(\mathbb{Z}, *,1)$ . But enough about numbers.

Implementing Monoids in C

Which monoids can we build in real code?

• $(String, +, "")$ — strings under concatenation;

• $(List, Concat(), {})$ — lists under list concatenation;

• $(Int32, max, -2^{31} + 1)$ — integers using maximum instead of addition;

• $(Boolean, ||, false)$ ;

And so on. First, let us express what we learned in code.

public interface ISemiGroup<T>
{
    T Plus(T left, T right);
}

public interface IMonoid<T> : ISemiGroup<T>
{
    T Zero { get; }
}

Update: As @Googolplex correctly noted, these interfaces are type classes. That comment made me rethink and improve the code in the article. The idea remains the same, but the implementation is slightly better. Instead of classes, we can implement these interfaces with structs. This reduces the cost of calling their functions and lets us use ad hoc polymorphism.

I deliberately called the operation "plus" and the identity element "zero." Spoiler: algebra has structures with two operations, such as rings, where "addition" must be distinguished from "multiplication." That distinction is not important here, though. Let us implement a maximum monoid.

public struct Max<T> : IMonoid<T> where T : IComparable<T>, new()
{
    public T Zero => new();

    public T Plus(T left, T right) =>
        left.CompareTo(right) > 0
            ? left
            : right;
}

Now we need some DTO to use with it.

public record Person(string Name, int Money) : IComparable<Person>
{
    public Person() : this("", int.MinValue)
    {
    }

    public int CompareTo(Person other) => Money.CompareTo(other.Money);
}

This leads to an important point. I am not going to take just two people and find the richer one. I need to process many people. I have a list.

var people = new List<Person>
{
    new("Bob", 1000),
    new("Tim", 1239),
    new("Jeff", 2000000000)
};

In other words, we can use these structures for different kinds of aggregation. With monoids, we could even write an extension like this:

public static class EnumerableExtensions
{
    public static T Sum<T, M>(this IEnumerable<T> collection, M monoid = default)
        where M : struct, IMonoid<T> =>
        collection.Aggregate(monoid.Zero, monoid.Plus);
}

What to do next is obvious:

var richest = people.Sum<Person, Max<Person>>();

Magic! Primitive magic, perhaps—for now. What other common aggregation do we have? The average. It turns out that calculating an average can be parallelized. This is not immediately obvious, but consider what an average consists of: a count and a sum. We need to track those two values separately. That gives us a structure analogous to $(\mathbb{Z}^2,+,(0,0))$ . Let us put that idea into code.

public class AveragedValue
{
    private double _sum;
    private int _count;

    public AveragedValue() : this(0, 0)
    {
    }

    public AveragedValue(double sum, int count = 1)
    {
        _sum = sum;
        _count = count;
    }

    public double Get() => _sum == 0
        ? 0
        : _sum / _count;

    public static AveragedValue operator +(AveragedValue av1, AveragedValue av2)
    {
        var newCount = av1._count + av2._count;
        var newSum = av1._sum + av2._sum;
        return new AveragedValue(newSum, newCount);
    }
}

public struct Avg : IMonoid<AveragedValue>
{
    public AveragedValue Plus(AveragedValue left, AveragedValue right) => left + right;

    public AveragedValue Zero => new();
}

That is better, but I would still like a real problem. One came to mind. I once needed to build a text filter for a table field, but there were so many conditions that the result looked ugly:

public bool Fits(string text) =>
    text ... ||
    text ... ||
    text ... ||
    ...;

What if the customer wants a different filter for another field, or a more flexible filter? I do not want to duplicate this tangle of conditionals, so let us look at the problem differently. A filter is a predicate: a Boolean function, or more formally, a mapping from a given type to the set of truth values. If we "add" predicates using logical OR, we get a monoid.

public struct Any<T> : IMonoid<Predicate<T>>
{
    public Predicate<T> Zero => _ => false;

    public Predicate<T> Plus(Predicate<T> left, Predicate<T> right) =>
        x => left(x) || right(x);
}

We can then compose the predicates without hard-coding each condition:

var predicates = new List<Predicate<char>>
{
    x => x >= '0' && x <= '9',
    x => x >= 'A' && x <= 'Z',
    x => x >= 'a' && x <= 'z'
};
var digitOrLetter = predicates.Sum<Predicate<char>, Any<char>>();

We can build a more interesting monoid over dictionaries and a merge operation. Let us require the dictionary values to form at least a semigroup, because conflicts will be resolved by adding the elements. The result looks like this:

public struct MapMonoid<K, V, S> : IMonoid<Dictionary<K, V>>
    where S : struct, ISemiGroup<V>
{
    public Dictionary<K, V> Zero => new();

    public Dictionary<K, V> Plus(Dictionary<K, V> left, Dictionary<K, V> right)
    {
        var valueSemiGroup = default(S);
        var result = Zero;
        foreach (var (key, value) in left.Concat(right))
        {
            result[key] = result.ContainsKey(key)
                ? valueSemiGroup.Plus(result[key], value)
                : value;
        }
        return result;
    }
}

How can we use it? Suppose we have a list of strings.

var strings = new List<string> { "foo", "foo", "foo", "bar", "bar", "baz", "pipi", "pupu" };

We can group the strings by occurrence count, find words of the same length, or implement any other idea you have.

var dicts = strings
    .Select(x => new Dictionary<string, int> { { x, 1 } });
var anotherDicts = strings
    .Select(x => new Dictionary<int, List<string>>
    {
        { x.Length, new List<string> { x } }
    });

Now add them using the appropriate semigroups: numbers under addition and lists under concatenation.

private struct IntSemiGroup : ISemiGroup<int>
{
    public int Plus(int left, int right) => left + right;
}

private struct ListSemiGroup<T> : ISemiGroup<List<T>>
{
    public List<T> Plus(List<T> left, List<T> right)
    {
        var result = new List<T>(left);
        result.AddRange(right);
        return result;
    }
}

var map = dicts
    .Sum<Dictionary<string, int>, MapMonoid<string, int, IntSemiGroup>>();
var anotherMap = anotherDicts
    .Sum<Dictionary<int, List<string>>, MapMonoid<int, List<string>, ListSemiGroup<string>>>();

This produces the following output:

When Algebraic Abstractions Help C# Code

Algebraic abstractions earn their place when the laws give you something concrete: safe regrouping, parallel aggregation, reusable composition, or clearer tests. If a named structure only makes familiar code harder to read, keep the direct implementation.

The practical takeaway is to look for associative operations and identity values in recurring aggregation code. Once those properties are explicit, a single generic reduction can replace several unrelated-looking loops without hiding their behavior.

---

Follow StepOne on GitHub for open-source C#/.NET projects, compiler experiments, production-focused examples, and new releases.

Algebraic code on GitHub