# ploeh blog danish software design

## Colour-mixing magma

*Mixing RGB colours forms a magma. An example 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 see an example of a magma, which is a binary operation without additional constraints.

### RGB colours #

The opening article about monoids, semigropus, and their friends emphasised Eric Evans' pigment mixing example from Domain-Driven Design. The following article series then promptly proceeded to ignore that example. The reason is that while the example has *Closure of Operations*, it exhibits precious few other properties. It's neither monoid, semigroup, quasigroup, nor any other named binary operation, apart from being a magma.

Instead of *pigments*, consider a more primitive, but well-understood colour model: that of RGB colours. In C#, you can model RGB colours using a `struct`

that holds three `byte`

fields. In my final code base, I ended up implementing `==`

, `!=`

, `Equals`

, and so on, but I'm not going to bore you with all of those details. Here's the `RgbColor`

constructor, so that you can get a sense of the type:

private readonly byte red; private readonly byte green; private readonly byte blue; public RgbColor(byte red, byte green, byte blue) { this.red = red; this.green = green; this.blue = blue; }

As you can see, `RgbColor`

holds three `byte`

fields, one for red, green, and blue. If you want to mix two colours, you can use the `MixWith`

instance method:

public RgbColor MixWith(RgbColor other) { var newRed = ((int)this.red + (int)other.red) / 2m; var newGreen = ((int)this.green + (int)other.green) / 2m; var newBlue = ((int)this.blue + (int)other.blue) / 2m; return new RgbColor( (byte)Math.Round(newRed), (byte)Math.Round(newGreen), (byte)Math.Round(newBlue)); }

This is a binary operation, because it's an instance method on `RgbColor`

, taking another `RgbColor`

as input, and returning `RgbColor`

. Since it's a binary operation, it's a magma, but could it be another, stricter category of operation?

### Lack of associativity #

Could `MixWith`

, for instance, be a semigroup? In order to be a semigroup, the binary operation must be associative, and while it can be demanding to prove that an operation is *always* associative, it only takes a single counter-example to prove that it's not:

[Fact] public void MixWithIsNotAssociative() { // Counter-example var x = new RgbColor( 67, 108, 13); var y = new RgbColor( 33, 114, 130); var z = new RgbColor( 38, 104, 245); Assert.NotEqual( x.MixWith(y).MixWith(z), x.MixWith(y.MixWith(z))); }

This xUnit.net unit test passes, thereby demonstrating that `MixWith`

is *not* associative. When you mix `x`

with `y`

, you get #326F48, and when you mix that with `z`

you get #2C6C9E. On the other hand, when you mix `y`

with `z`

you get #246DBC, which, combined with `x`

, gives #346C64. #2C6C9E is not equal to #346C64, so the `NotEqual`

assertion passes.

Because of this counter-example, `MixWith`

isn't associative, and therefore not a semigroup. Since monoid requires associativity as well, we can also rule out that `MixWith`

is a monoid.

### Lack of invertibility #

While `MixWith`

isn't a semigroup, could it be a quasigroup? In order to be a quasigroup, a binary operation must be invertible. This means that for *any* two elements `a`

and `b`

, there must exist two other elements `x`

and `y`

that turns `a`

into `b`

.

This property must hold for all values involved in the binary operation, so again, a single counter-example suffices to demonstrate that `MixWith`

isn't invertible, either:

[Fact] public void MixWithIsNotInvertible() { // Counter-example var a = new RgbColor( 94, 35, 172); var b = new RgbColor(151, 185, 7); Assert.False(RgbColor.All.Any(x => a.MixWith(x) == b)); Assert.False(RgbColor.All.Any(y => y.MixWith(a) == b)); }

This xUnit.net-based test also passes. It uses brute force to demonstrate that for all `RgbColor`

values, there's no `x`

and `y`

that satisfy the invertibility property. The test actually takes a while to execute, because `All`

returns all 16,777,216 possible `RgbColor`

values:

private static RgbColor[] all; private readonly static object syncLock = new object(); public static IReadOnlyCollection<RgbColor> All { get { if (all == null) lock (syncLock) if (all == null) { var max = 256 * 256 * 256; all = new RgbColor[max]; foreach (var i in Enumerable.Range(0, max)) all[i] = (RgbColor)i; } return all; } }

For performance reasons, the `All`

property uses lazy initialisation with double-checked locking. It simply counts from `0`

to `256 * 256 * 256`

(16,777,216) and converts each integer to an `RgbColor`

value using this explicit conversion:

public static explicit operator RgbColor(int i) { var red = (i & 0xFF0000) / 0x10000; var green = (i & 0xFF00) / 0x100; var blue = i & 0xFF; return new RgbColor((byte)red, (byte)green, (byte)blue); }

The bottom line, though, is that the test passes, thereby demonstrating that for the chosen counter-example, no `x`

and `y`

satisfies the invertibility property. Therefore, `MixWith`

isn't a quasigroup.

### Lack of identity #

Since `MixWith`

is neither associative nor invertible, it's not really any named algebraic construct, other than a magma. It's neither group, semigroup, quasigroup, monoid, loop, groupoid, etc. Does it have *any* properties at all, apart from being a binary operation?

It doesn't have identity either, which you can illustrate with another counter-example:

[Fact] public void MixWithHasNoIdentity() { var nearBlack = new RgbColor(1, 1, 1); var identityCandidates = from e in RgbColor.All where nearBlack.MixWith(e) == nearBlack select e; // Verify that there's only a single candidate: var identityCandidate = Assert.Single(identityCandidates); // Demonstrate that the candidate does behave like identity for // nearBlack: Assert.Equal(nearBlack, nearBlack.MixWith(identityCandidate)); Assert.Equal(nearBlack, identityCandidate.MixWith(nearBlack)); // Counter-example var counterExample = new RgbColor(3, 3, 3); Assert.NotEqual( counterExample, counterExample.MixWith(identityCandidate)); }

The counter-example starts with a near-black colour. The reason I didn't pick absolute black (`new RgbColor(0, 0, 0)`

) is that, due to rounding when mixing, there are eight candidates for absolute black, but only one for `nearBlack`

. This is demonstrated by the `Assert.Single`

assertion. `identityCandidate`

, by the way, is also `new RgbColor(1, 1, 1)`

, and further Guard Assertions demonstrate that `identityCandidate`

behaves like the identity for `nearBlack`

.

You can now pick another colour, such as `new RgbColor(3, 3, 3)`

and demonstrate that `identityCandidate`

does *not* behave like the identity for the counter-example. Notice that the assertion is `Assert.NotEqual`

.

If an identity exists for a magma, it must behave as the identity for all possible values. That's demonstrably not the case for `MixWith`

, so it doesn't have identity.

### Commutativity #

While `MixWith`

is neither associative, invertible, nor has identity, it does have at least one property: it's commutative. This means that the order of the input values doesn't matter. In other words, for any two `RgbColor`

values `x`

and `y`

, this assertion always passes:

```
Assert.Equal(
x.MixWith(y),
y.MixWith(x));
```

Since `x.MixWith(y)`

is equal to `y.MixWith(x)`

, `MixWith`

is commutative.

### Summary #

The `MixWith`

operation is a commutative magma, but while, for example, we call an associative magma a *semigroup*, there's no fancy word for a commutative magma.

In this article, you got another, fairly realistic, example of a binary operation. Throughout the overall article series on monoids, semigroup, and other group-like algebraic structures, you've seen many examples, and you've learned how to analyse binary operations for the presence or absence of various properties. The present article concludes the series. You can, however, continue reading the even more overall article series.

## Rock Paper Scissors magma

*The Rock Paper Scissors game forms a magma. An example 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 see an example of a magma, which is a binary operation without additional constraints.

### Rock Paper Scissors #

When my first child was born, my wife and I quickly settled on a first name, but we couldn't agree on the surname, since we don't share the same surname. She wanted our daughter to have her surname, and I wanted her to have mine. We couldn't think of any rational arguments for one or the other, so we decided to settle the matter with a game of Rock Paper Scissors. I lost, so my daughter has my wife's surname.

Despite that outcome, I still find that Rock Paper Scissors is a great way to pick between two equally valid alternatives. You could also flip a coin, or throw a die, but most people have their hands handy, so to speak.

In C#, you can model the three shapes of rock, paper, and scissors like this:

public abstract class Rps { public readonly static Rps Rock = new R(); public readonly static Rps Paper = new P(); public readonly static Rps Scissors = new S(); private Rps() { } private class R : Rps { } private class P : Rps { } private class S : Rps { } // More members... }

I've seen more than one example where people use an enum to model the three shapes, but I believe that this is wrong, because `enum`

s have an order to them, including a maximum and a minimum value (by default, `enum`

is implemented with a 32-bit integer). That's not how Rock Paper Scissors work, so instead, I chose a different model where `Rock`

, `Paper`

, and `Scissors`

are Singletons.

This design works for the example, although I'm not entirely happy with it. The problem is that Rock, Paper, and Scissors should be a finite set, but by making `Rps`

abstract, another developer could, conceivably, create additional derived classes. A finite sum type would have been better, but this isn't easily done in C#. In a language with algebraic data types, you can make a prettier implementation, like this Haskell example. F# would be another good language option.

### Binary operation #

When playing the game of Rock Paper Scissors, each round is a *throw* that compares two shapes. You can model a throw as a binary operation that returns the winning shape:

public static Rps Throw(Rps x, Rps y) { if (x == Rock && y == Rock) return Rock; if (x == Rock && y == Paper) return Paper; if (x == Rock && y == Scissors) return Rock; if (x == Paper && y == Paper) return Paper; if (x == Paper && y == Scissors) return Scissors; if (x == Paper && y == Rock) return Paper; if (x == Scissors && y == Scissors) return Scissors; if (x == Scissors && y == Rock) return Rock; return Scissors; }

To a C# programmer, perhaps the method name `Throw`

is bewildering, because you might expect the method to throw an exception, but I chose to use the domain language of the game.

Because this method takes two `Rps`

values as input and returns an `Rps`

value as output, it's a binary operation. Thus, you already know it's a magma, but could it, also, be another, stricter binary operations, such as a semigroup or quasigroup?

### Lack of associativity #

In order to be a semigroup, the binary operation must be associative. You can easily demonstrate that `Throw`

isn't associative by use of a counter-example:

[Fact] public void ThrowIsNotAssociative() { // Counter-example Assert.NotEqual( Rps.Throw(Rps.Throw(Rps.Paper, Rps.Rock), Rps.Scissors), Rps.Throw(Rps.Paper, Rps.Throw(Rps.Rock, Rps.Scissors))); }

This xUnit.net unit test passes, thereby demonstrating that `Throw`

is *not* associative. The result of paper versus rock is paper, which, pitted against scissors yields scissors. On the other hand, paper versus the result of rock versus scissors is paper, because rock versus scissors is rock, and rock versus paper is paper.

Since `Throw`

isn't associative, it's not a semigroup (and, by extension, not a monoid). Could it be a quasigroup?

### Lack of invertibility #

A binary operation must be invertible in order to be a quasigroup. This means that for *any* two elements `a`

and `b`

, there must exist two other elements `x`

and `y`

that turns `a`

into `b`

.

This property must hold for all values involved in the binary operation - in this case `Rock`

, `Paper`

, and `Scissors`

. A single counter-example is enough to show that `Throw`

is *not* invertible:

[Fact] public void ThrowIsNotInvertible() { // Counter-example var a = Rps.Rock; var b = Rps.Scissors; Assert.False(Rps.All.Any(x => Rps.Throw(a, x) == b)); Assert.False(Rps.All.Any(y => Rps.Throw(y, a) == b)); }

This (passing) unit test utilises an `All`

property on `Rps`

:

public static IReadOnlyCollection<Rps> All { get { return new[] { Rock, Paper, Scissors }; } }

For a counter-example, pick `Rock`

as `a`

and `Scissors`

as `b`

. There's no value in `All`

that satisfies the invertibility property. Therefore, `Throw`

is not a quasigroup, either.

### Lack of identity #

Since `Throw`

is neither associative nor invertible, it's not really any named algebraic construct, other than a magma. It's neither group, semigroup, quasigroup, monoid, loop, groupoid, etc. Does it have *any* properties at all, apart from being a binary operation?

It doesn't have identity either, which you can illustrate with another counter-example:

[Fact] public void ThrowHasNoIdentity() { // Find all identity candidates for Rock var rockIdentities = from e in Rps.All where Rps.Throw(e, Rps.Rock) == Rps.Rock && Rps.Throw(Rps.Rock, e) == Rps.Rock select e; // Narrow for Paper var paperIdentities = from e in rockIdentities where Rps.Throw(e, Rps.Paper) == Rps.Paper && Rps.Throw(Rps.Paper, e) == Rps.Paper select e; // None of those candidates are the identity for Scissors var scissorIdentities = from e in paperIdentities where Rps.Throw(e, Rps.Scissors) == Rps.Scissors && Rps.Throw(Rps.Scissors, e) == Rps.Scissors select e; Assert.Empty(scissorIdentities); }

First, you use `Rps.All`

to find all the values that behave as an identity element for `Rps.Rock`

. Recall that the identity is an element that doesn't change the input. In other words it's a value that when combined with `Rps.Rock`

in `Throw`

still returns `Rps.Rock`

. There are two values that fulfil that property: `Rps.Rock`

and `Rps.Scissors`

. Those are the two values contained in `rockIdentities`

.

In order to be an identity, the value must behave as a neutral element for *all* possible values, so next, filter `rockIdentities`

to find those elements that also behave as identities for `Rps.Paper`

. Between `Rps.Rock`

and `Rps.Scissors`

, only `Rps.Rock`

behaves like an identity for `Rps.Paper`

, so `paperIdentities`

is a collection containing only the single value `Rps.Rock`

.

Is `Rps.Rock`

an identity for `Rps.Scissors`

, then? It's not. `scissorIdentities`

is empty. There's no element in `Rps.All`

that acts an identity for all values in `Rps.All`

. Therefore, by brute force, the test `ThrowHasNoIdentity`

demonstrates (as it says on the tin) that throw has no identity.

### Commutativity #

While `Throw`

is neither associative, invertible, nor has identity, it does have at least one property: it's commutative. This means that the order of the input values doesn't matter. In other words, for any two `Rps`

values `x`

and `y`

, this assertion always passes:

Assert.Equal( Rps.Throw(x, y), Rps.Throw(y, x));

Since `Rps.Throw(x, y)`

is equal to `Rps.Throw(y, x)`

, `Throw`

is commutative.

### Summary #

The Rock Paper Scissors `Throw`

operation is a commutative magma, but while, for example, we call an associative magma a *semigroup*, there's no fancy word for a commutative magma.

**Next:** Colour-mixing magma.

## Magmas

*A binary operation with no constraints on its behaviour is called a magma. An introduction for object-oriented programmers.*

In the overall article series about group-like algebraic structures, you've so far seen examples of monoids, semigroups, and quasigroups. Common to all of these structures is that they are binary operations governed by at least one law. The laws are different for the different categories, but there *are* rules.

What if you have a binary operation that follows none of those rules?

All binary operations are magmas. If they have additional properties, we may call them *quasigroups*, or *monoids*, or some such, depending on the specific properties, but they're still all magmas. This is the most inclusive category.

You've already seen examples of monoids and semigroups, but what about magma examples? In a sense, you've already seen those as well, because all the examples you've seen so far have also been magma examples. After all, since all monoids are magmas, all the monoid examples you've seen have also been magma examples.

Still, it's not that hard to come up with some programming examples of magmas that aren't semi- or quasigroups. In the next articles, you'll see some examples.

Particularly the second example is fairly realistic, which demonstrates that as programmers, we can benefit from having vocabulary that enables us to describe any binary operation that doesn't obey any particular laws. In fact, establishing a vocabulary has been my primary motivation for writing this article series.## Quasigroups

*A brief introduction to quasigroups 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 get acquainted with the concept of a quasigroup. I don't think it plays that big of a role in software design, but it *is* a thing, and I thought that I'd cover it briefly with a well known-example.

During all this talk of monoids and semigroups, you've seen that normal arithmetic operations like addition and multiplication form monoids. Perhaps you've been wondering where subtraction fits in.

Subtraction forms a quasigroup.

What's a quasigroup? It's an invertible binary operation.

### Inversion #

What does it mean for a binary operation to be invertible? It means that for any two elements `a`

and `b`

, there must exist two other elements `x`

and `y`

that turns `a`

into `b`

.

This is true for subtraction, as this FsCheck-based test demonstrates:

[Property(QuietOnSuccess = true)] public void SubtractionIsInvertible(int a, int b) { var x = a - b; var y = a + b; Assert.True(a - x == b); Assert.True(y - a == b); }

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 any `a`

and `b`

generated by FsCheck, we can calculate unique `x`

and `y`

that satisfy `a - x == b`

and `y - a == b`

.

Subtraction isn't the only invertible binary operation. In fact, addition is also invertible:

[Property(QuietOnSuccess = true)] public void AdditionIsInvertible(int a, int b) { var x = b - a; var y = b - a; Assert.True(a + x == b); Assert.True(y + a == b); Assert.Equal(x, y); }

Here I added a third assertion that demonstrates that for addition, the inversion is symmetric; `x`

and `y`

are equal.

Not only is integer addition a monoid - it's also a quasigroup. In fact, it's a group. Being associative or having identity doesn't preclude a binary operation from being a quasigroup, but these properties aren't required.

### No identity #

No identity element exists for integer subtraction. For instance, *3 - 0* is *3*, but *0 - 3* is *not 3*. Therefore, subtraction can't be a monoid.

### No associativity #

Likewise, subtraction is not an associative operation. You can easily convince yourself of that by coming up with a counter-example, such as *(3 - 2) - 1*, which is *0*, but different from *3 - (2 - 1)*, which is *2*. Therefore, it can't be a semigroup either.

### Summary #

A quasigroup is an invertible binary operation. Invertibility is the only *required* property of a quasigroup (apart from being a binary operation), but if it has other properties (like associativity), it's still a quasigroup.

I haven't had much utility from thinking about software design in terms of quasigroups, but I wanted to include it in case you were wondering how subtraction fits into all of this.

What if, however, you have a binary operation with *no other* properties?

**Next:** Magmas.

## Semigroups accumulate

*You can accumulate an arbitrary, non-zero number of semigroup values to a single value. An article for object-oriented programmers.*

This article is part of a series about semigroups. In short, a *semigroup* is an associative binary operation.

As you've learned in a previous article, you can accumulate an arbitrary number of monoidal values to a single value. A corresponding property holds for semigroups.

### Monoid accumulation #

When an instance method `Op`

forms a monoid, you can easily write a function that accumulates an arbitrary number of `Foo`

values:

public static Foo Accumulate(IReadOnlyCollection<Foo> foos) { var acc = Identity; foreach (var f in foos) acc = acc.Op(f); return acc; }

Notice how this generally applicable algorithm starts with the `Identity`

value. One implication of this is that when `foos`

is empty, the return value will be `Identity`

. When `Op`

is a semigroup, however, there's no identity, so this doesn't quite work. You need a value to start the accumulation; something you can return if the collection is empty.

### Semigroup accumulation #

From Haskell you can learn that if you have a semigroup, you can accumulate any non-empty collection:

`sconcat :: Semigroup a => NonEmpty a -> a`

You can read this as: for any generic type `a`

, when `a`

forms a `Semigroup`

, the `sconcat`

function takes a non-empty list of `a`

values, and reduces them to a single `a`

value. `NonEmpty a`

is a list with at least one element.

### NotEmptyCollection #

You can also define a `NotEmptyCollection<T>`

class in C#:

public class NotEmptyCollection<T> : IReadOnlyCollection<T> { public NotEmptyCollection(T head, params T[] tail) { if (head == null) throw new ArgumentNullException(nameof(head)); this.Head = head; this.Tail = tail; } public T Head { get; } public IReadOnlyCollection<T> Tail { get; } public int Count { get => this.Tail.Count + 1; } public IEnumerator<T> GetEnumerator() { yield return this.Head; foreach (var item in this.Tail) yield return item; } IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } }

Because of the way the constructor is defined, you *must* supply at least one element in order to create an instance. You can provide any number of extra elements via the `tail`

array, but one is minimum.

The `Count`

property returns the number of elements in `Tail`

, plus one, because there's always a `Head`

value.

The `GetEnumerator`

method returns an iterator that always starts with the `Head`

value, and proceeds with all the `Tail`

values, if there are any.

### Finding the maximum of a non-empty collection #

As you've already learned, `Math.Max`

is a semigroup. Although the .NET Base Class Library has built-in methods for this, you can use a generally applicable algorithm to find the maximum value in a non-empty list of integers.

private static int Accumulate(NotEmptyCollection<int> numbers) { var acc = numbers.Head; foreach (var n in numbers.Tail) acc = Math.Max(acc, n); return acc; }

Notice how similar this algorithm is to monoid accumulation! The only difference is that instead of using `Identity`

to get started, you can use `Head`

, and then loop over all elements of `Tail`

.

You can use it like this:

var nec = new NotEmptyCollection<int>(42, 1337, 123); var max = Accumulate(nec);

Here, `max`

is obviously `1337`

.

As usual, however, this is much nicer, and more succinct in Haskell:

Prelude Data.Semigroup Data.List.NonEmpty> getMax $ sconcat $ fmap Max $ 42 :| [1337, 123] 1337

That's hardly the idiomatic way of getting a maximum element in Haskell, but it does show how you can 'click together' concepts in order to achieve a goal.

### Aggregate #

Perhaps the observant reader will, at this point, have recalled to him- or herself that the .NET Base Class Library already includes an `Aggregate`

extension method, with an overload that takes a seed. In general, the simpliest `Aggregate`

method doesn't gracefully handle empty collections, but using the overload that takes a seed is more robust. You can rewrite the above `Accumulate`

method using `Aggregate`

:

private static int Accumulate(NotEmptyCollection<int> numbers) { return numbers.Tail.Aggregate( numbers.Head, (x, y) => Math.Max(x, y)); }

Notice how you can pass `Head`

as the seed, and accumulate the `Tail`

using that starting point. The `Aggregate`

method is more like Haskell's `sconcat`

for semigroups than `mconcat`

for monoids.

### Summary #

A semigroup operation can be used to reduce values to a single value, just like a monoid can. The only difference is that a semigroup operation can't reduce an empty collection, whereas a monoid can.

**Next:** Quasigroups

## Bounding box semigroup

*A semigroup example 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 see a non-trivial example of a semigroup that's *not* a monoid. In short, a semigroup is an associative binary operation.

### Shapes #

Imagine that you're developing a library of two-dimensional shapes, and that, for various reasons, each shape should have a *bounding box*. For example, here's a blue circle with a green bounding box:

The code for a circle shape could look like this:

public class Circle : ICanHasBox { public int X { get; } public int Y { get; } public int Radius { get; } public Circle(int x, int y, int radius) { this.X = x; this.Y = y; this.Radius = Math.Abs(radius); } public BoundingBox BoundingBox { get { return new BoundingBox( this.X - this.Radius, this.Y - this.Radius, this.Radius * 2, this.Radius * 2); } } }

In addition to the `Circle`

class, you could have other shapes, such as rectangles, triangles, or even irregular shapes, each of which have a bounding box.

### Bounding box unions #

If you have two shapes, you also have two (green) bounding boxes, but perhaps you'd like to find the (orange) bounding box of the union of both shapes.

That's fairly easy to do:

public BoundingBox Unite(BoundingBox other) { var newX = Math.Min(this.X, other.X); var newY = Math.Min(this.Y, other.Y); var newRightX = Math.Max(this.rightX, other.rightX); var newTopY = Math.Max(this.topY, other.topY); return new BoundingBox( newX, newY, newRightX - newX, newTopY - newY); }

The `Unite`

method is an instance method on the `BoundingBox`

class, so it's a binary operation. It's also associative, because for all `x`

, `y`

, and `z`

, `isAssociative`

is `true`

:

`var isAssociative = x.Unite(y).Unite(z) == x.Unite(y.Unite(z));`

Since the operation is associative, it's at least a semigroup.

### Lack of identity #

Is `Unite`

also a monoid? In order to be a monoid, a binary operation must not only be associative, but also have an identity element. In a previous article, you saw how the union of two convex hulls formed a monoid. A bounding box seems to be conceptually similar to a convex hull, so you'd be excused to think that our previous experience applies here as well.

It doesn't.

There's no *identity bounding box*. The difference between a convex hull and a bounding box is that it's possible to define an empty hull as an empty set of coordinates. A bounding box, on the other hand, always has a coordinate and a size.

public struct BoundingBox { private readonly int rightX; private readonly int topY; public int X { get; } public int Y { get; } public int Width { get; } public int Height { get; } // More members, including Unite... }

An identity element, if one exists, is one where if you `Unite`

it with another `BoundingBox`

object, the return value will be the other object.

Consider, then, a (green) `BoundingBox x`

. Any other `BoundingBox`

inside of `x`

, including `x`

itself, is a candidate for an identity element:

In a real coordinate system, there's infinitely many candidates contained in `x`

. As long as a candidate is wholly contained within `x`

, then the union of the candidate and `x`

will return `x`

.

In the code example, however, coordinates are 32-bit integers, so for any bounding box `x`

, there's only a finite number of candidates. Even for the smallest possible bounding box, though, the box itself is an identity candidate.

In order to be an identity element, however, the *same* element must behave as the identity element for *all* bounding boxes. It is, therefore, trivial to find a counter-example:

Just pick any other `BoundingBox y`

outside of `x`

. Every identity candidate must be within `x`

, and therefore the union of the candidate and `y`

cannot be `y`

.

In code, you can demonstrate the lack of identity with an FsCheck-based test like this:

[Property(QuietOnSuccess = true)] public Property UniteHasNoIdentity(PositiveInt w, PositiveInt h) { var genCandidate = from xi in Gen.Choose(1, w.Get) from yi in Gen.Choose(1, h.Get) from wi in Gen.Choose(1, w.Get - xi + 1) from hi in Gen.Choose(1, h.Get - yi + 1) select new BoundingBox(xi, yi, wi, hi); return Prop.ForAll( genCandidate.ToArbitrary(), identityCandidate => { var x = new BoundingBox(1, 1, w.Get, h.Get); // Show that the candidate behaves like identity for x Assert.Equal(x, x.Unite(identityCandidate)); Assert.Equal(x, identityCandidate.Unite(x)); // Counter-example var y = new BoundingBox(0, 0, 1, 1); Assert.NotEqual(y, y.Unite(identityCandidate)); }); }

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 passes.

It follows the above 'proof' by first generating an identity candidate for `x`

. This is any `BoundingBox`

contained within `x`

, including `x`

itself. In order to keep the code as simple as possible, `x`

is always placed at the coordinate *(1, 1)*.

The test proceeds to utilise two Guard Assertions to show that `identityCandidate`

does, indeed, behave like an identity for `x`

.

Finally, the test finds a trivial counter-example in `y`

, and verifies that `y.Unite(identityCandidate)`

is not equal to `y`

. Therefore, `identityCandidate`

is *not* the identity for `y`

.

`Unite`

is a semigroup, but not a monoid, because no identity element exists.

### Summary #

This article demonstrates (via an example) that non-trivial semigroups exist in normal object-oriented programming.

**Next:** Semigroups accumulate.

## Semigroups

*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.

## Monoids accumulate

*You can accumulate an arbitrary number of monoidal values to a single value. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a *monoid* is an associative binary operation with a neutral element (also known as *identity*).

Recall that a binary operation is an operation involving two arguments of the same type, and returning a value of that type.

public static Foo Op(Foo x, Foo y)

Notice that such an operation reduces two `Foo`

values to a single `Foo`

value.

### Accumulation #

Since you have an operation that can reduce two values to a single value, you can use that single value as the input for yet another binary operation. This enables you to accumulate, or aggregate, an arbitrary number of values.

Consider the instance variation of the above `Op`

method:

public Foo Op(Foo foo)

This is another representation of the operation, but instead of being a static method, it's an instance method on the `Foo`

class.

When `Op`

is a monoid, you can easily write a function that accumulates an arbitrary number of `Foo`

values:

public static Foo Accumulate(IReadOnlyCollection<Foo> foos) { var acc = Identity; foreach (var f in foos) acc = acc.Op(f); return acc; }

You start with the `Identity`

value, which also becomes the return value if `foos`

is empty. Then you simply loop over each value in `foos`

and use `Op`

with the value accumulated so far (`acc`

) and the current element in the sequence.

Once you're done looping, you return the accumulator.

This implementation isn't always guaranteed to be the most efficient, but you can *always* write accumulation like that. Sometimes, a more efficient algorithm exists, but that doesn't change the overall result that you can always reduce an arbitrary number of values whenever a monoid exists for those values.

### Generalisation #

You can do this with any monoid. In Haskell, this function is called `mconcat`

, and it has this type:

mconcat :: Monoid a => [a] -> a

The way you can read this is that for any monoid `a`

, `mconcat`

is a function that takes a linked list of `a`

values as input, and returns a single `a`

value as output.

This function seems both more general, and more constrained, than the above C# example. It's more general than the C# example because it works on any monoid, instead of just `Foo.Op`

. On the other hand, it seems more limited because it works only on Haskell lists. The C# example, in contrast, can accumulate any `IReadOnlyCollection<Foo>`

. Could you somehow combine those two generalisations?

Nothing stops you from doing that, but it's already in Haskell's `Data.Foldable`

module:

fold :: (Monoid m, Foldable t) => t m -> m

The way to read this is that there's a function called `fold`

, and it accumulates any monoid `m`

contained in any 'foldable' data container `t`

. That a data container is 'foldable' means that there's a way to somehow fold, or aggregate, the element(s) in the container into a value.

Linked lists, arrays, and other types of sequences are foldable, as are Maybe and trees.

In fact, there's little difference between Haskell's `Foldable`

type class and .NET's `IEnumerable<T>`

, but as the names suggest, their foci are different. In Haskell, the focus is being able to fold, accumulate, or aggregate a data structure, whereas on .NET the focus is on being able to enumerate the values inside the data structure. Ultimately, though, both abstractions afford the same capabilities.

In .NET, the focal abstraction is the Iterator pattern, which enables you to enumerate the values in the data container. On top of that abstraction, you can derive other behaviour, such as the ability to Aggregate data.

In Haskell, the focus is on the ability to fold, but from that central abstraction follows the ability to convert the data container into a linked list, which you can then enumerate.

### Summary #

You can accumulate an arbitrary number of monoidal values as long as they're held in a container that enables you to 'fold' it. This includes all sorts of lists and arrays.

This article concludes the article series about monoids. In the next series of articles, you'll learn about a related category of operations.

**Next: ** Semigroups.

## Comments

@ploeh as always I loved your blog post but I don't 100% agree on your comparison of the iterator pattern with Foldable - the iterator pattern allows usually sideeffects and you have Traversable for that - you might also like this: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf …

(Comment submitted via Twitter)

## Endomorphism monoid

*A method that returns the same type of output as its input forms a monoid. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a *monoid* is an associative binary operation with a neutral element (also known as *identity*). Methods that return the same type of value as their input form monoids over composition. The formal term for such an operation is an endomorphism.

### Scheduling example #

Imagine that you have to develop some functionality for scheduling events in the future. As a concrete example, I recently wrote about adjusting dates while taking bank holidays into account. For instance, if you want to find the latest bank day *before* a given date, you could call the `AdjustToLatestPrecedingDutchBankDay`

method. If you give it a normal bank day (say, a Thursday), it'll simply return the input date, but if you give it a Sunday, it'll return the preceding Friday. That is, unless that particular Friday is a bank holiday, in which case it'll return the Thursday before - as long as that's not also a bank holiday, and so on.

In that previous article, the `AdjustToLatestPrecedingDutchBankDay`

method is an extension method, but you can also model it as an instance method, like this:

public DateTimeOffset Adjust(DateTimeOffset value) { var candidate = value; while (!(IsDutchBankDay(candidate.DateTime))) candidate = candidate.AddDays(-1); return candidate; }

This method would be part of a class that implements an interface:

public interface IDateTimeOffsetAdjustment { DateTimeOffset Adjust(DateTimeOffset value); }

You can make other implementations of this interface. Here's one that adjusts a date and time to business hours:

public class BusinessHoursAdjustment : IDateTimeOffsetAdjustment { private readonly static TimeSpan startOfBussiness = TimeSpan.FromHours(9); private readonly static TimeSpan endOfBusiness = TimeSpan.FromHours(17); public DateTimeOffset Adjust(DateTimeOffset value) { // Warning: May not handle DST changes appropriately! // It's only example code... if (value.TimeOfDay < startOfBussiness) return value - value.TimeOfDay + startOfBussiness; if (endOfBusiness < value.TimeOfDay) return (value - value.TimeOfDay + startOfBussiness).AddDays(1); return value; } }

To keep the example simple, business hours are hard-coded to 9-17.

You could also adapt conversion to UTC:

public class UtcAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value.ToUniversalTime(); } }

Or add a month:

public class NextMonthAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value.AddMonths(1); } }

Notice that the `Adjust`

method returns a value of the same type as its input. So far when discussing monoids, we've been looking at binary operations, but `Adjust`

is a *unary* operation.

An operation that returns the same type as its input is called an *endomorphism*. Those form monoids.

### Composing adjustments #

It's easy to connect two adjustments. Perhaps, for example, you'd like to first use `BusinessHoursAdjustment`

, followed by the bank day adjustment. This will adjust an original input date and time to a date and time that falls on a bank day, within business hours.

You can do this in a general-purpose, reusable way:

public static IDateTimeOffsetAdjustment Append( this IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y) { return new AppendedAdjustment(x, y); } private class AppendedAdjustment : IDateTimeOffsetAdjustment { private readonly IDateTimeOffsetAdjustment x; private readonly IDateTimeOffsetAdjustment y; public AppendedAdjustment( IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y) { this.x = x; this.y = y; } public DateTimeOffset Adjust(DateTimeOffset value) { return y.Adjust(x.Adjust(value)); } }

The `Append`

method takes two `IDateTimeOffsetAdjustment`

values and combines them by wrapping them in a private implementation of `IDateTimeOffsetAdjustment`

. When `AppendedAdjustment.Adjust`

is called, it first calls `Adjust`

on `x`

, and then calls `Adjust`

on `y`

with the return value from the first call.

In order to keep the example simple, I omitted null guards, but apart from that, `Append`

should work with any two implementations of `IDateTimeOffsetAdjustment`

. In other words, it obeys the Liskov Substitution Principle.

### Associativity #

The `Append`

method is a binary operation. It takes two `IDateTimeOffsetAdjustment`

values and returns an `IDateTimeOffsetAdjustment`

. It's also associative, as a test like this demonstrates:

private void AppendIsAssociative( IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y, IDateTimeOffsetAdjustment z) { Assert.Equal( x.Append(y).Append(z), x.Append(y.Append(z))); }

As usual in this article series, such a test doesn't *prove* that `Append`

is associative for all values of `IDateTimeOffsetAdjustment`

, but if you run it as a property-based test, it demonstrates that it's quite likely.

### Identity #

In true monoidal fashion, `IDateTimeOffsetAdjustment`

also has an identity element:

public class IdentityDateTimeOffsetAdjustment : IDateTimeOffsetAdjustment { public DateTimeOffset Adjust(DateTimeOffset value) { return value; } }

This implementation simply returns the input value without modifying it. That's a neutral operation, as a test like this demonstrates:

private void AppendHasIdentity(IDateTimeOffsetAdjustment x) { Assert.Equal( x.Append(new IdentityDateTimeOffsetAdjustment()), x); Assert.Equal( new IdentityDateTimeOffsetAdjustment().Append(x), x); }

These two assertions verify that left and right identity holds.

Since `Append`

is associative and has identity, it's a monoid.

This holds generally for any method (or function) that returns the same type as it takes as input, i.e. `T SomeOperation(T x)`

. This matches the built-in library in Haskell, where `Endo`

is a `Monoid`

.

### Conclusion #

A method that returns a value of the same type as its (singular) input argument is called an endomorphism. You can compose two such unary operations together in order to get a composed operation. You simply take the output of the first method and use it as the input argument for the second method. That composition is a monoid. Endomorphisms form monoids.

**Next:** Maybe monoids.

## Comments

Hi, Mark!

I'm really enjoing your series on category theory. I think you're doing a great job in making such abstract concepts accessible to us programmers. However, I found this particular episode puzzling. You claim that any composition of endomorphisms is a monoid, and you also claim to have tested that your `Append`

method is associative. However, it is not hard to come up with a counter-example:

[Fact] public void CounterExample() { IDateTimeOffsetAdjustment weekend = new WeekendAdjustment(); IDateTimeOffsetAdjustment nextMonth = new NextMonthAdjustment(); var a = new AppendedAdjustment(weekend, nextMonth); var b = new AppendedAdjustment(nextMonth, weekend); var startDate = new DateTimeOffset(2019, 1, 5, 0, 0, 0, TimeSpan.Zero); Assert.Equal(a.Adjust(startDate), b.Adjust(startDate)); }

Here, `WeekendAdjustment`

is just a simplified `DutchBankDayAdjustment`

.

It would also be interesting to see how you can do property based testing on this, i.e. how to automatically generate meaningful instances of `IDateTimeOffsetAdjustment`

. When I try to run your test, I get: "IDateTimeOffsetAdjustment is not handled automatically by FsCheck. Consider using another type or writing and registering a generator for it."

Tor, thank you for writing, and for your kind words. I suppose that the `CounterExample`

test fails when one executes it; you don't explicitly write that, but that's what I expect would happen.

The `Append`

operation is, indeed, not commutative. This is, however, not a requirement for monoids, or even for groups. Some monoids, such as addition and multiplication, are also commutative, while others, like list concatenation or, here, the endomorphism monoid, aren't.

When it comes to the FsCheck properties, I admit that I cheated slightly with the code listing in the article. I did this because the properties are a bit more complicated than what I show, and I was concerned that the extra infrastructure surrounding those tests would detract from the overall message.

The associativity property in its entirety looks like this:

[Property(QuietOnSuccess = true)] public Property AppendIsAssociative() { return Prop.ForAll( GenerateAdjustment().Three().ToArbitrary(), t => AppendIsAssociative(t.Item1, t.Item2, t.Item3)); } private void AppendIsAssociative( IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y, IDateTimeOffsetAdjustment z) { Assert.Equal( x.Append(y).Append(z), x.Append(y.Append(z)), new DateTimeOffsetAdjustmentComparer()); }

Where `GenerateAdjustment`

is defined like this:

private static Gen<IDateTimeOffsetAdjustment> GenerateAdjustment() { return Gen.Elements<IDateTimeOffsetAdjustment>( new IdentityDateTimeOffsetAdjustment(), new BusinessHoursAdjustment(), new DutchBankDayAdjustment(), new NextMonthAdjustment(), new UtcAdjustment()); }

Not only did I omit all that extra scaffolding, I also pretended that `IDateTimeOffsetAdjustment`

objects could be compared using their default implementations of `Equals`

, which they meaningfully can't. Notice that the full property listed here also asserts using a custom equality comparer:

private class DateTimeOffsetAdjustmentComparer : IEqualityComparer<IDateTimeOffsetAdjustment> { public bool Equals(IDateTimeOffsetAdjustment x, IDateTimeOffsetAdjustment y) { var rnd = new System.Random(); var dt = new DateTimeOffset(rnd.Next(), TimeSpan.Zero); return x.Adjust(dt) == y.Adjust(dt); } public int GetHashCode(IDateTimeOffsetAdjustment obj) { return 0; } }

The custom comparer's `Equals`

method creates a random number of ticks and uses it to create a `DateTimeOffset`

value. It then calls `Adjust`

on both objects, which are considered equal if they produce the same result.

The test for identity is defined in a similar fashion; it also uses `GenerateAdjustment`

and `DateTimeOffsetAdjustmentComparer`

.

Thank you for such a prompt and thorough reply. You are of course correct, I have been confusing associativity with commutativity. I didn't run into the same mistake during the list concatenation article, though, maybe because list concatenation more obviously is associative and not commutative. In the current article, however, I intuitively felt that the operations needed to be commutative, but your reply clears that up.

It is also helpful to see the extra scaffolding around your property based test. The article itself seemed to imply that instances of `IDateTimeOffsetAdjustment`

could be automatically generated. Your approach to set up such a test will come in handy now that I'm convinced that I should let more of my tests be property based, even in C#!

Tor, I made the same mistake several times when I started researching all of this. I think that there's something intuitive and fundamental about commutativity, so at a superficial glance, it seems odd that we can do without it, while at the same time requiring a less intuitive property like associativity.

When it comes to computation, though, I think that it's exactly the nature of associativity that enables us to decompose big problems into several small problems. The order of how you deal with those small problems doesn't matter, as long as you apply the intermediate results in the correct order.

Dear Mark!

These additional explanations and contextual information in the comment sections deserve a place in the original text. To keep the text uncluttered this site uses clickable popups: . If you click on some of the numbers, you'll see what I mean. You might consider adding this feature to the text.

Best regards, Norbert.

## Function monoids

*Methods are monoids if they return monoids. An article for object-oriented programmers.*

This article is part of a series about monoids. In short, a *monoid* is an associative binary operation with a neutral element (also known as *identity*).

### Functions #

In statically typed C-languages, like C# or Java, methods are typically declared like this:

public Foo Bar(Baz baz, Qux qux)

As you'll see in another article, however, you can refactor any method to a method that takes a single argument as input, and returns a single (possibly complex) value as output. In abstract form, we can write it like this:

public Out1 Op1(In1 arg)

Another way to abstract a method is by using generics:

public T Op1<T1, T>(T1 x)

Another article demonstrates how this is similar to a generic function. In F#, for instance, the type of the function would be written as `'a -> 'b`

, whereas in Haskell it'd be written `a -> b`

. The way to read this is that the function takes a value of the generic type `T1`

/`'a`

/`a`

as input, and returns a value of the generic type `T`

/`'b`

/`b`

as output. For the rest of this article, I'll favour the Haskell syntax, since it has minimal noise.

To be clear, however, although I favour the Haskell syntax because of its succinctness, I don't mean to imply that the functions that I discuss are exclusively pure - think of an F# function `'a -> 'b`

which may or may not be pure.

### Binary combination of functions #

A function `a -> b`

is a monoid if `b`

is a monoid. This means that you can combine two functions with the same type. In an object-oriented context, it means that you can combine two methods with the same signature into one method as long as the return type forms a monoid.

Consider the following (facetious) C# example. You're trying to establish how secure a GUID is. Primes are important in cryptography, so the more primes a GUID contains, the better... right?

private const string primes = "2357bd"; public static int CountPrimes(Guid g) { return g.ToString("N").Count(primes.Contains); }

The `CountPrimes`

method counts the number of prime digits in a given GUID. So far so good, but you also think that hexadecimal notation is more exotic than decimal notation, so surely, the digits A-F are somehow more secure, being more unfamiliar. Thus, you have a method to count those as well:

private const string letters = "abcdef"; public static int CountLetters(Guid g) { return g.ToString("N").Count(letters.Contains); }

Good, but both of these numbers are, clearly, excellent indicators of how secure a GUID is. Which one should you choose? Both of them, of course!

Can you combine `CountPrimes`

and `CountLetters`

? Yes, you can, because, while GUIDs don't form a monoid, the return type `int`

forms a monoid over addition. This enables you to write a `Combine`

method:

public static Func<Guid, int> Combine( Func<Guid, int> f, Func<Guid, int> g) { return x => f(x) + g(x); }

Notice that `Combine`

takes two `Func<Guid, int>`

values and return a new `Func<Guid, int>`

value. It's a binary operation. Here's an example of how to use it:

var calculateSecurity = Combine(CountPrimes, CountLetters); var actual = calculateSecurity(new Guid("10763FF5-E3C8-46D1-A70F-6C1D9EDA8120")); Assert.Equal(21, actual);

Now you have an excellent measure of the security strength of GUIDs! 21 isn't *that* good, though, is it?

Antics aside, `Combine`

is a binary function. Is it a monoid?

### Monoid laws #

In order to be a monoid, `Combine`

must be associative, and it is, as the following FsCheck property demonstrates:

[Property(QuietOnSuccess = true)] public void CombineIsAssociative( Func<Guid, int> f, Func<Guid, int> g, Func<Guid, int> h, Guid guid) { Assert.Equal( Combine(Combine(f, g), h)(guid), Combine(f, Combine(g, h))(guid)); }

In this property-based test, FsCheck generates three functions with the same signature. Since functions don't have structural equality, the easiest way to compare them is to call them and see whether they return the same result. This explains why the assertion invokes both associative combinations with `guid`

. The test passes.

In order to be a monoid, `Combine`

must also have an identity element. It does:

public static Func<Guid, int> FuncIdentity = _ => 0;

This is simply a function that ignores its input and always returns `0`

, which is the identity value for addition. The following test demonstrates that it behaves as expected:

[Property(QuietOnSuccess = true)] public void CombineHasIdentity(Func<Guid, int> f, Guid guid) { Assert.Equal(f(guid), Combine(FuncIdentity, f)(guid)); Assert.Equal(f(guid), Combine(f, FuncIdentity)(guid)); }

As was the case with `CombineIsAssociative`

, in order to assert that the combined functions behave correctly, you have to call them. This, again, explains why the assertion invokes the combined functions with `guid`

. This test passes as well.

`Combine`

is a monoid.

### Generalisation #

While the above C# code is only an example, the general rule is that any function that returns a monoid is itself a monoid. In Haskell, this rule is articulated in the standard library:

instance Monoid b => Monoid (a -> b)

This means that for any monoid `b`

, a function `a -> b`

is also (automatically) a monoid.

### Summary #

A function or method with a return type that forms a monoid is itself a monoid.

**Next: ** Endomorphism monoid.

## Comments

Thanks

Yacoub, thank you for writing. The operation used here isn't the

intersection, but rather theunionof two bounding boxes; that's the reason I called the method`Unite`

.Hello Mark. I am aware of this, but maybe I did not explain my self correctly.

What I am trying to say is that when coming up with a counter-example, we should choose a BoundingBox y wholly outside of x (not just partially outside of x).

If we choose a BoundingBox y partially outside of x, then the intersection between x and y (the BoundingBox z = the area shared between x and y) is a valid identity element.

Yacoub, I think you're right; sorry about that!

Perhaps I should have written

Just pick any otherWould that have been correct?`BoundingBox y`

partially or wholly outside of the candidate.That would be correct. I am not sure though if this is the best way to explain it.

y being wholly ourside of x seems better to me.

Yacoub, I've corrected the text in the article. Thank you for the feedback!