Lord of the Algebras: Groups, Rings, and Semirings in C#

The same matrix algorithm can count paths, find shortest paths, or find longest paths. The data structure does not change; the algebra assigned to its operations does. That is the practical payoff of modeling groups, rings, and semirings instead of hard-coding arithmetic.

Last time, we met semigroups and monoids. Algebra did not end there. As the previous article showed, moving forward means placing more constraints on the operation defined over the structure's carrier set. But how do we know which direction to take?

Much of the original interest in this field grew out of questions about equations. The exact questions do not matter here; the important word is equations.

Assume from this point onward that we have a structure and some abstract binary operation. Take the pair $(G, \circ)$ , which we call a monoid. We can choose any $a$ and $b$ from $G$ , compute $a \circ b$ , and obtain some $c \in G$ . Fine. But what if we are asked this?

$$\begin{gathered} a \circ x = b \ a, x, b \in G \ x = \; ? \end{gathered}$$

A monoid alone cannot answer. We can say that $x = a^{-1} \circ b$ , where $a^{-1}$ is the inverse of $a$ , and $a$ is invertible. Formally, $a$ is invertible if:

$$\exists \; h = a^{-1}: a \circ h = h \circ a = e$$

But a monoid does not guarantee that every element is invertible. There is, however, a way out.

Groups in C#

Not every element of a monoid is invertible. A monoid may nevertheless contain invertible elements, and they form a subset. That subset is a group. A group is a monoid in which every element has an inverse. This is our next constraint—the third axiom.

$$\forall \; g \in G \; \exists \; h=g^{-1} \in G: g \circ h = h \circ g = e$$

public interface IGroup<T> : IMonoid<T>
{
    T Inverse(T item);
}

Inside a group, our equation $a \circ x = b$ always has a solution.

What makes groups interesting? Every object, whatever its nature, has an opposite: an inverse, a reversal, a symmetry. You may have heard group theory described as the mathematics of symmetry.

There is even a symmetric group $S_n$ . It contains every bijection that rearranges a set of $n$ elements. A readable representation uses two rows: $1...n$ on top, and their destinations below. For an arbitrary $\phi \in S_3$ :

$$\phi = \begin{pmatrix} 1 & 2& 3 \ 2&3&1 \end{pmatrix}$$

The first element moves to the second position, the second to the third, and the third to the first. Composition is defined by $(\phi \circ \pi) (i) = \pi (\phi(i))$ . To find the inverse, swap and reorder the rows: $\phi(i) = j \implies \phi^{-1}(j) =i$ .

Permutation.cs

public class Permutation : IEquatable<Permutation>
{
    private readonly int[] _map;

    public Permutation(params int[] map)
    {
        _map = new int[map.Length];
        for (var i = 0; i < map.Length; i++)
        {
            _map[i] = map[i];
        }
    }

    public int this[int index] => _map[index];

    public bool Equals(Permutation other)
    {
        if (other != null && _map.Length == other._map.Length)
        {
            return _map.Zip(other._map)
                .All(pair => pair.First == pair.Second);
        }
        return false;
    }

    public override string ToString() =>
        new StringBuilder()
            .AppendJoin(' ', Enumerable.Range(1, _map.Length))
            .Append('\n')
            .AppendJoin(' ', _map.Select(x => x + 1))
            .ToString();
}

SymmetricGroup.cs

public readonly struct SymmetricGroup : IGroup<Permutation>
{
    private readonly int _length;

    public SymmetricGroup(int length)
    {
        _length = length;
    }

    public Permutation Plus(Permutation left, Permutation right)
    {
        var newMap = new int[_length];
        for (var i = 0; i < _length; i++)
        {
            newMap[i] = right[left[i]];
        }
        return new Permutation(newMap);
    }

    public Permutation Zero =>
        new(Enumerable.Range(0, _length).ToArray());

    public Permutation Inverse(Permutation item)
    {
        var newMap = new int[_length];
        for (var i = 0; i < _length; i++)
        {
            newMap[item[i]] = i;
        }
        return new Permutation(newMap);
    }
}

For the solution $x = b \circ a^{-1}$ , the operation $\circ$ must also be commutative. Restricting groups this way gives Abelian groups $G$ :

$$\forall \; g, h \in G : g \circ h = h \circ g$$

That is enough theory to get a feel for the concept. Let us turn to something more practical.

Suppose we want an append-only catalog. We can record only changes—events that happened to the catalog.

public record CatalogueEvent<T>;

public record Add<T>(T Data) : CatalogueEvent<T>;

public record Remove<T>(T Data) : CatalogueEvent<T>;

public record Nothing<T> : CatalogueEvent<T>;

We also need to traverse its elements and obtain an aggregate. Each catalog item maps into a monoid element so it can be aggregated. Where do groups enter the picture?

The problem contains a symmetry: we can add or remove, and those actions are opposites. A group lets the event-to-aggregate mapping preserve that relationship.

public class Catalogue<T> : IEnumerable<CatalogueEvent<T>>
{
    private readonly List<CatalogueEvent<T>> _catalogueEvents = new();

    public S Reduce<S, G>(Func<T, S> map, G group = default)
        where G : struct, IGroup<S>
        => _catalogueEvents.Select(t =>
            t switch
            {
                Add<T> add => map(add.Data),
                Remove<T> rm => group.Inverse(map(rm.Data)),
                Nothing<T> => group.Zero,
                _ => default
            }
        ).Sum<S, G>();

    public Catalogue<T> Add(T item)
    {
        _catalogueEvents.Add(new Add<T>(item));
        return this;
    }

    public Catalogue<T> Remove(T item)
    {
        _catalogueEvents.Add(new Remove<T>(item));
        return this;
    }

    public Catalogue<T> Nothing()
    {
        _catalogueEvents.Add(new Nothing<T>());
        return this;
    }

    public IEnumerator<CatalogueEvent<T>> GetEnumerator() =>
        _catalogueEvents.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() =>
        GetEnumerator();
}

Reduce performs exactly that mapping. map targets a monoid, aggregation uses the earlier article's Sum extension, and narrowing the monoid to a group gives every Remove event the inverse of its object.

var stringsCatalogue = new Catalogue<string>()
    .Add("abc")
    .Nothing()
    .Remove("c")
    .Remove("a")
    .Add("ed");

IntAddGroup.cs

private struct IntAddGroup : IGroup<int>
{
    public int Plus(int left, int right) => left + right;

    public int Zero => 0;

    public int Inverse(int item) => -item;
}

For example, obtain the resulting string length:

stringsCatalogue.Reduce<int, IntAddGroup>(s => s.Length); // 3

The catalog may not feel strongly motivated yet, but the mechanism clearly works. What if we want to reconstruct the resulting string? Concatenation gives strings a monoid, but there is no obvious string subtraction. We can imagine:

"abc" - "c" == "ab"

But what should "abc" - "d", "" - "", or "" - "xyz" mean? The question has no answer under those rules, but there is still a way forward.

We might model a string as an IEnumerable<char> and generalize from sets to collections. Union makes sets only a commutative monoid. Symmetric difference gives an Abelian group, but not the behavior we want.

Track inclusions and exclusions separately instead: represent a set as a pair of sets, with elements to include on the left and elements to exclude on the right.

PairedHashSet.cs

public record PairedSet<T>(HashSet<T> First, HashSet<T> Second)
{
    public PairedSet() : this(new(), new())
    {
    }

    public PairedHashSet(IEnumerable<T> single) : this(new(single), new())
    {
    }
}

public static class PairedSetExtensions
{
    public static HashSet<T> ToHashSet<T>(this PairedSet<T> pairedSet)
    {
        var (first, second) = pairedSet;
        return first.Except(second);
    }
}

public static class HashSetExtensions
{
    public static HashSet<T> Except<T>(this HashSet<T> first, HashSet<T> second)
    {
        var result = new HashSet<T>(first);
        result.ExceptWith(second);
        return result;
    }

    public static HashSet<T> Union<T>(this HashSet<T> first, HashSet<T> second)
    {
        var result = new HashSet<T>(first);
        result.UnionWith(second);
        return result;
    }
}

public struct PairedHashSetGroup<T> : IGroup<PairedHashSet<T>>
{
    public PairedHashSet<T> Plus(PairedHashSet<T> left, PairedHashSet<T> right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedHashSet<T>(newLeft, newRight);
    }

    public PairedHashSet<T> Zero => new();

    public PairedHashSet<T> Inverse(PairedHashSet<T> item)
    {
        var (first, second) = item;
        return new PairedHashSet<T>(second, first);
    }
}

The same logic transfers easily to lists, where we can choose whether to remove from the beginning or the end.

PairedList.cs

public record PairedList<T>(List<T> First, List<T> Second)
{
    public PairedList() : this(new(), new())
    {
    }

    public PairedList(IEnumerable<T> single) : this(new(single), new())
    {
    }
}

public static class PairedListExtensions
{
    public static List<T> ToList<T>(this PairedList<T> pairedList)
    {
        var (first, second) = pairedList;
        return first.Except(second);
    }
}

public static class ListExtensions
{
    public static List<T> Union<T>(this List<T> list, List<T> items)
    {
        var result = new List<T>(list);
        result.AddRange(items);
        return result;
    }

    public static List<T> Except<T>(this List<T> first, List<T> second)
    {
        var result = new List<T>(first);
        second.ForEach(item =>
        {
            var li = result.LastIndexOf(item);
            if (li > -1)
            {
                result.RemoveAt(li);
            }
        });
        return result;
    }
}

PairedListGroup.cs

public struct PairedListGroup<T> : IGroup<PairedList<T>>
{
    public PairedList<T> Plus(PairedList<T> left, PairedList<T> right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedList<T>(newLeft, newRight);
    }

    public PairedList<T> Zero => new();

    public PairedList<T> Inverse(PairedList<T> item)
    {
        var (first, second) = item;
        return new PairedList<T>(second, first);
    }
}

Returning to the catalog, we can test the result:

var chars = stringsCatalogue.Reduce<PairedList<char>, PairedListGroup<char>>(
    s => new PairedList<char>(s)).ToList();
Console.WriteLine(string.Join("", chars)); // bed

We can also aggregate catalog events into the final collection by mapping every object to a singleton paired list.

// немного расширим список конструкторов
public record PairedList<T>(List<T> First, List<T> Second)
{
    ...
    public PairedList(T item) : this(new List<T> { item })
    {
    }
}

public static class CatalogueExtensions
{
    public static List<T> Collect<T>(this Catalogue<T> catalogue) =>
        catalogue.Reduce<PairedList<T>, PairedListGroup<T>>(
            x => new PairedList<T>(x)
        ).ToList();
}

This even works for an arbitrary DTO:

public record SomeDto(int Number, bool Flag, string Field)
{
}

var someDtosCatalogue = new Catalogue<SomeDto>()
    .Add(new SomeDto(1, false, "asa"))
    .Add(new SomeDto(2, true, "asa"))
    .Remove(new SomeDto(1, false, "asa"));

Get the collection's size:

someDtosCatalogue.Reduce<int, IntAddGroup>(_ => 1)

Or retrieve the collection itself:

var someDtosObjects = someDtosCatalogue.Collect();
someDtosObjects.ForEach(Console.WriteLine);
// SomeDto { Number = 2, Flag = True, Field = asa }

Or inspect the log:

var logs = someDtosCatalogue.ToList();
logs.ForEach(Console.WriteLine);
// Add { Data = SomeDto { Number = 1, Flag = False, Field = asa } }
// Add { Data = SomeDto { Number = 2, Flag = True, Field = asa } }
// Remove { Data = SomeDto { Number = 1, Flag = False, Field = asa } }

We have spent long enough on groups. Time to move on.

Rings in C#

The Pythagorean theorem says that a right triangle with sides $a, b, c$ satisfies $a^2 + b^2 = c^2$ . People have long studied triangles whose sides are integers. Eventually all such triples were described, but generalization continued.

Mathematicians and programmers share a desire to generalize. The formula is a special case of the Diophantine equation $x^n + y^n = z^n$ . In 1637, Pierre de Fermat stated that no integer triples exist for natural $n > 2$ . This historical problem helped set the stage for ring theory.

Early proof attempts handled specific values of $n$ by studying divisibility in sets such as $\mathbb{Z}[\sqrt{-n}]= { a + b\sqrt{-n}: a,b \in \mathbb{Z} }$ . Their elements behaved like integers, creating a need to generalize integer arithmetic. That is how the concept of a ring arose.

A commutative ring is a set $R$ with operations $+$ and $\times$ such that:

• $(R, +)$ is an Abelian group.
• $(R, \times)$ is a commutative monoid.
• $\times$ distributes over $+$ on both sides: $\forall \; a, b, c \in R : (a + b) \times c = a \times c + b \times c$ .

public interface IRing<T> : IGroup<T>
{
    T One { get; }

    T Times(T left, T right);
}

The remaining examples are more toy-like, but no less interesting. Rings generalize integer arithmetic and are useful when multiplication needs to be generalized. Let us therefore use non-numeric structures.

A homomorphism is a mapping between two structures that preserves their operation. For structures $(G, \oplus)$ and $(H, \otimes)$ , $\phi: G \to H$ is a homomorphism if:

$$\forall \; x, y \in X \; \phi(x \oplus y) = \phi(x) \otimes \phi(y)$$

Homomorphisms are an abstract class of mappings: they may be surjective, injective, endomorphic, and so on. The most important is an isomorphism, a bijection preserving the operation. Two isomorphic structures have the same operational behavior and a one-to-one correspondence, so we can move between them freely.

For example, real numbers under addition $(\mathbb{R}, +)$ and positive reals under multiplication $(\mathbb{R}+^*, *)$ are groups connected by $x \mapsto e^x$ . Why study both separately when one can be described _up to isomorphism?

An endomorphism is a homomorphism from a structure to itself. All endomorphisms of $S$ form $End(S)$ . If $S$ is an Abelian group, $End(S)$ is a ring under pointwise addition and function composition.

public struct End<T, G> : IRing<Func<T, T>>
    where G : struct, IGroup<T>
{
    public Func<T, T> Plus(Func<T, T> left, Func<T, T> right) =>
        x => default(G).Plus(left(x), right(x));

    public Func<T, T> Zero => _ => default(G).Zero;

    public Func<T, T> Inverse(Func<T, T> item) =>
        x => default(G).Inverse(x);

    public Func<T, T> One => x => x;

    public Func<T, T> Times(Func<T, T> left, Func<T, T> right) =>
        x => left(right(x));
}

Let us use End<T, G> to build a function producing powers of two. Add a singleton constructor to PairedHashSet<T> and an extension that computes a ring power.

RingExtensions.cs

public static class RingExtensions
{
    public static T Power<T>(this IRing<T> ring, T item, int n)
    {
        var result = item;
        for (var i = 1; i < n; i++)
        {
            result = ring.Times(result, item);
        }
        return result;
    }
}

var end = default(End<PairedHashSet<int>, PairedHashSetGroup<int>>);
var id = end.One;
Func<PairedHashSet<int>, PairedHashSet<int>> x2 =
    s => new(s.ToHashSet().Select(i => i * 2));
var idPlusX2 = end.Plus(id, x2);
var pows = end.Power(idPlusX2, 6)(new(1)); // {1, 2, 4, 8, 16, 32, 64}

Semirings for Graph Algorithms

Like a group, a ring has a "semi" counterpart. A semiring is a triple $(S, +, \times)$ such that:

• $(S, +)$ is a commutative monoid.
• $(S, \times)$ is a monoid.
• Multiplication distributes over addition.
• Zero is absorbing: $\forall \; x \in S \; x \times 0 = 0 = 0 \times x$ .

public interface ISemiRing<T> : IMonoid<T>
{
    T One { get; }

    T Times(T left, T right);
}

Unlike a ring, a semiring does not require additive inverses; the zero law compensates for the absence of formal subtraction. Examples where it fails are available here.

Semirings have many practical applications. This book, for example, shows mathematically how a broad class of graph problems can be solved uniformly by generalizing matrix multiplication and adapting the incidence matrix.

Treat matrices not as systems of numbers but as systems of arbitrary elements with an algebra. For all $n \times n$ matrices $M_n(S)$ over a semiring $(S, \oplus, \otimes)$ , define multiplication as:

$$c_{ij} = \bigoplus_{k = 1}^n a_{ik} \otimes b_{kj}$$

public class SquareMatrix<T, S> : IEnumerable<SquareMatrix<T, S>.Vector>
    where S : struct, ISemiRing<T>
{
    private readonly int _size;
    private readonly List<Vector> _rows = new();

    public SquareMatrix(int size)
    {
        _size = size;
        for (var i = 0; i < _size; i++)
        {
            _rows.Add(new Vector(
                Enumerable.Repeat(default(S).Zero, _size)
            ));
        }
    }

    public SquareMatrix(int size, params IEnumerable<T>[] rows)
    {
        _size = size;
        _rows.AddRange(rows.Select(x => new Vector(x)));
    }

    public T this[int i, int j]
    {
        get => _rows[i][j];
        set => _rows[i][j] = value;
    }

    public SquareMatrix<T, S> Transpose()
    {
        var columns = Enumerable
            .Range(0, _size)
            .Select(i => _rows.Select(col => col[i]));
        return new(_size, columns.ToArray());
    }

    public SquareMatrix<T, S> Product(SquareMatrix<T, S> that)
    {
        var transposed = that.Transpose();
        var rows = this
            .Select(x => transposed.Select(x.Dot));
        return new(_size, rows.ToArray());
    }

    public SquareMatrix<T, S> Power(int n)
    {
        var result = this;
        for (var i = 1; i < n; i++)
        {
            result = result.Product(this);
        }
        return result;
    }

    public IEnumerator<Vector> GetEnumerator() => _rows.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public override string ToString() =>
        new StringBuilder()
            .AppendJoin('\n', _rows.Select(row =>
                new StringBuilder()
                    .Append('|')
                    .AppendJoin(", ", row)
                    .Append('|')))
            .ToString();

    public class Vector : IEnumerable<T>
    {
        private readonly List<T> _items;

        public Vector(IEnumerable<T> items)
        {
            _items = new List<T>(items);
        }

        public T this[int index]
        {
            get => _items[index];
            set => _items[index] = value;
        }

        public T Dot(Vector that) => _items
            .Zip(that._items)
            .Select(pair => default(S).Times(pair.First, pair.Second))
            .Sum<T, S>();

        public IEnumerator<T> GetEnumerator() => _items.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}

The semiring $(\mathbb{R} \cup { + \infty}, \min, +)$ finds the shortest path from $i$ to $j$ in at most $k$ steps. $(\mathbb{R} \cup { - \infty}, \max, +)$ analogously finds the longest path.

MinPlus.cs

public struct MinPlus : ISemiRing<double>
{
    public double Plus(double left, double right) => Min(left, right);

    public double Zero => double.PositiveInfinity;

    public double One => 0;

    public double Times(double left, double right) => left + right;
}

MaxPlus.cs

public struct MaxPlus : ISemiRing<double>
{
    public double Plus(double left, double right) => Max(left, right);

    public double Zero => double.NegativeInfinity;

    public double One => 0;

    public double Times(double left, double right) => left + right;
}

First verify exponentiation over the integer semiring:

SquareMatrix<int, IntSemiRing> testMatrix = new(3,
    new[] { 1, 0, 3 },
    new[] { 0, 5, 0 },
    new[] { 2, 0, 6 });
Console.WriteLine(testMatrix.Power(4));

The result is indeed:

$$\begin{pmatrix} 343 & 0 & 1029 \ 0 & 625 & 0 \ 686 & 0 & 2058 \end{pmatrix}$$

Now consider this graph:

Generalized matrix multiplication solves both problems by calculating $A^k_{ij}$ .

public class WeightedGraph
{
    private readonly int _size;
    private readonly Dictionary<int, List<(int Vertex, double Weight)>> _adjancencyList = new();

    public WeightedGraph(int size, params (int, List<(int Vertex, double Weight)>)[] adjancencyList)
    {
        _size = size;
        adjancencyList.ToList()
            .ForEach(x => _adjancencyList[x.Item1] = x.Item2);
    }

    private SquareMatrix<double, S> GetAdjacencyMatrix<S>()
        where S : struct, ISemiRing<double>
    {
        var adjancencyMatrix = new SquareMatrix<double, S>(_size);
        for (var i = 0; i < _size; i++)
        {
            adjancencyMatrix[i, i] = default(S).One;
        }
        foreach (var key in _adjancencyList.Keys)
        {
            foreach (var (vertex, weight) in _adjancencyList[key])
            {
                adjancencyMatrix[key, vertex] = weight;
            }
        }
        return adjancencyMatrix;
    }

    public double GetShortestPath(int i, int j, int k) =>
        GetAdjacencyMatrix<MinPlus>()
            .Power(k)[i, j];

    public double GetLongestPath(int i, int j, int k) =>
        GetAdjacencyMatrix<MaxPlus>()
            .Power(k)[i, j];
}

The shortest $a \to d$ path in at most three steps costs 8, while the longest in at most two steps costs 13.

var weightedGraph = new WeightedGraph(4,
    (0, new() { (1, 3), (2, 8), (3, 12) }),
    (1, new() { (2, 2), (3, 10) }),
    (2, new() { (3, 3) }));
Console.WriteLine(weightedGraph.GetShortestPath(0, 3, 3)); // 8
Console.WriteLine(weightedGraph.GetLongestPath(0, 3, 2)); // 13

When Groups, Rings, and Semirings Pay Off

Algebraic structures let one implementation operate over several meanings of “addition” and “multiplication.” In this example, changing the semiring changes the graph question while the matrix exponentiation code stays intact.

That reuse is valuable only if the laws hold and the abstraction remains understandable to the team. Test the identities and distributive laws for custom implementations, document what each operation means in the domain, and prefer direct code when there is only one concrete use case.

---

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

Algebraic code on GitHub