# Semigroups by Mark Seemann

*Introduction to semigroups for object-oriented programmers.*

This article is part of a larger series about monoids, semigroups, and other group-like algebraic structures. In this article, you'll learn what a semigroup is, and what distinguishes it from a monoid.

Semigroups form a superset of monoids. They are associative binary operations. While monoids additionally require that an identity element exists, no such requirement exist for semigroups. In other words, all monoids are semigroups, but not all semigroups are monoids.

This article gives you an overview of semigroups, as well as a few small examples. A supplemental article will show a more elaborate example.

### Minimum #

An operation that returns the smallest of two values form a semigroup. In the .NET Base Class Library, such an operation is already defined for many numbers, for example 32-bit integers. Since associativity is a property of a semigroup, it makes sense to demonstrate it with a property-based test, here using FsCheck:

[Property(QuietOnSuccess = true)] public void IntMinimumIsAssociative(int x, int y, int z) { Assert.Equal( Math.Min(Math.Min(x, y), z), Math.Min(x, Math.Min(y, z))); }

This example uses the FsCheck.Xunit glue library for xUnit.net. Notice that although FsCheck is written in F#, you can also use it from C#. This test (as well as all other tests in this article) passes.

For mathematical integers, no identity element exists, so the minimum operation doesn't form a monoid. In practice, however, .NET 32-bit integers *do* have an identity element:

[Property(QuietOnSuccess = true)] public void MimimumIntHasIdentity(int x) { Assert.Equal(x, Math.Min(int.MaxValue, x)); Assert.Equal(x, Math.Min(x, int.MaxValue)); }

Int32.MaxValue is the maximum possible 32-bit integer value, so it effectively behaves as the identity for the 32-bit integer minimum operation. All 32-bit numbers are smaller than, or equal to, `Int32.MaxValue`

. This effectively makes `Math.Min(int, int)`

a monoid, but conceptually, it's not.

This may be clearer if, instead of 32-bit integers, you consider BigInteger, which is an arbitrarily large (or small) integer. The *minimum* operation is still associative:

[Property(QuietOnSuccess = true)] public void BigIntMinimumIsAssociative( BigInteger x, BigInteger y, BigInteger z) { Assert.Equal( BigInteger.Min(BigInteger.Min(x, y), z), BigInteger.Min(x, BigInteger.Min(y, z))); }

No identity element exists, however, because no matter which integer you have, you can always find one that's bigger: no maximum value exists. This makes `BigInteger.Min`

a semigroup, but not a monoid.

### Maximum #

Like *minimum*, the *maximum* operation forms a semigroup, here demonstrated by `BigInteger.Max`

:

[Property(QuietOnSuccess = true)] public void BigIntMaximumIsAssociative( BigInteger x, BigInteger y, BigInteger z) { Assert.Equal( BigInteger.Max(BigInteger.Max(x, y), z), BigInteger.Max(x, BigInteger.Max(y, z))); }

Again, like minimum, no identity element exists because the set of integers is infinite; you can always find a bigger or smaller number.

Minimum and maximum operations aren't limited to primitive numbers. If values can be compared, you can always find the smallest or largest of two values, here demonstrated with `DateTime`

values:

[Property(QuietOnSuccess = true)] public void DateTimeMaximumIsAssociative( DateTime x, DateTime y, DateTime z) { Func<DateTime, DateTime, DateTime> dtMax = (dt1, dt2) => dt1 > dt2 ? dt1 : dt2; Assert.Equal( dtMax(dtMax(x, y), z), dtMax(x, dtMax(y, z))); }

As was the case with 32-bit integers, however, the presence of DateTime.MinValue effectively makes `dtMax`

a monoid, but *conceptually*, no identity element exists, because dates are infinite.

### First #

Another binary operation simply returns the first of two values:

public static T First<T>(T x, T y) { return x; }

This may seem pointless, but `First`

*is* associative:

[Property(QuietOnSuccess = true)] public void FirstIsAssociative(Guid x, Guid y, Guid z) { Assert.Equal( First(First(x, y), z), First(x, First(y, z))); }

On the other hand, there's no identity element, because there's no *left identity*. The *left identity* is an element `e`

such that `First(e, x) == x`

for any `x`

. Clearly, for any generic type `T`

, no such element exists because `First(e, x)`

will only return `x`

when `x`

is equal to `e`

. (There are, however, degenerate types for which an identity exists for `First`

. Can you find an example?)

### Last #

Like `First`

, a binary operation that returns the last (second) of two values also forms a semigroup:

public static T Last<T>(T x, T y) { return y; }

Similar to `First`

, `Last`

is associative:

[Property(QuietOnSuccess = true)] public void LastIsAssociative(String x, String y, String z) { Assert.Equal( Last(Last(x, y), z), Last(x, Last(y, z))); }

As is also the case for `First`

, no identity exists for `Last`

, but here the problem is the lack of a *right identity*. The *right identity* is an element `e`

for which `Last(x, e) == x`

for all `x`

. Clearly, `Last(x, e)`

can only be equal to `x`

if `e`

is equal to `x`

.

### Aggregation #

Perhaps you think that operations like `First`

and `Last`

seem useless in practice, but when you have a semigroup, you can reduce any non-empty sequence to a single value. In C#, you can use the Aggregate LINQ method for this. For example

var a = new[] { 1, 0, 1337, -10, 42 }.Aggregate(Math.Min);

returns `-10`

, while

var a = new[] { 1, 0, 1337, -10, 42 }.Aggregate(Math.Max);

returns `1337`

. Notice that the input sequence is the same in both examples, but the semigroup differs. Likewise, you can use `Aggregate`

with `First`

:

var a = new[] { 1, 0, 1337, -10, 42 }.Aggregate(First);

Here, `a`

is `1`

, while

var a = new[] { 1, 0, 1337, -10, 42 }.Aggregate(Last);

returns `42`

.

LINQ has specialised methods like Min, Last, and so on, but from the perspective of behaviour, `Aggregate`

would have been enough. While there may be performance reasons why some of those specialised methods exist, you can think of all of them as being based on the same abstraction: that of a semigroup.

`Aggregate`

, and many of the specialised methods, throw an exception if the input sequence is empty. This is because there's no identity element in a semigroup. The method doesn't know how to create a value of the type `T`

from an empty list.

If, on the other hand, you have a monoid, you can return the identity element in case of an empty sequence. Haskell explicitly makes this distinction with `sconcat`

and `mconcat`

, but I'm not going to go into that now.

### Summary #

Semigroups are associative binary operations. In the previous article series about monoids you saw plenty of examples, and since all monoids are semigroups, you've already seen more than one semigroup example. In this article, however, you saw four examples of semigroups that are *not* monoids.

All four examples in this article are simple, and may not seem like 'real-world' examples. In the next article, then, you'll get a more realistic example of a semigroup that's not a monoid.

**Next:** Bounding box semigroup.