# ploeh blog danish software design

## Function isomorphisms

*Instance methods are isomorphic to functions.*

This article is part of a series of articles about software design isomorphisms.

While I have already, in an earlier article, quoted the following parable about Anton, Qc Na, objects, and closures, it's too good a fit to the current topic to pass up, so please pardon the duplication.

The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."

Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.

The point is that objects and closures are two ways of looking at a thing. In a nutshell, objects are data with behaviour, whereas closures are behaviour with data. I've already shown an elaborate C# example of this, so in this article, you'll get a slightly more formal treatment of the subject.

### Isomorphism #

In object-oriented design, you often bundle operations as methods that belong to objects. These are isomorphic to static methods, because a lossless translation exists. We can call such static methods *functions*, although they aren't guaranteed to be pure.

In the spirit of Refactoring, we can describe each translation as a refactoring, because that's what it is. I don't think the book contains a specific refactoring that describes how to translate from an instance method to a static method, but we could call it *Replace Object with Argument*.

Going the other way is, on the other hand, already described, so we can use Refactoring's *Move Method*.

### Replace Object with Argument #

While the concept of refactoring ought to be neutral across paradigms, the original book is about object-oriented programming. In object-oriented programming, objects are the design ideal, so it didn't make much sense to include, in the book, a refactoring that turns an instance method into a static method.

Nevertheless, it's straightforward:

- Add an argument to the instance method. Declare the argument as the type of the hosting class.
- In the method body, change all calls to
`this`

and`base`

to the new argument. - Make the method static.

`Baz`

method:

public class Foo { public Bar Baz(Qux qux, Corge corge) { // Do stuff, return bar } // Other members... }

You'll first introduce a new `Foo foo`

argument to `Baz`

, change the method body to use `foo`

instead of `this`

, and then make the method static. The result is this:

public class Foo { public static Bar Baz(Foo foo, Qux qux, Corge corge) { // Do stuff, return bar } // Other members... }

Once you have a static method, you can always move it to another class, if you'd like. This can, however, cause some problems with accessibility. In C#, for example, you'd no longer be able to access `private`

or `protected`

members from a method outside the class. You can choose to leave the static method reside on the original class, or you can make the member in question available to more clients (make it `internal`

or `public`

).

### Move Method #

The book Refactoring doesn't contain a recipe like the above, because the goal of that book is better object-oriented design. It would consider a static method, like the second variation of `Baz`

above, a code smell named *Feature Envy*. You have this code smell when it looks as if a method is more interested in one of its arguments than in its host object. In that case, the book suggests using the *Move Method* refactoring.

The book already describes this refactoring, so I'm not going to repeat it here. Also, there's no sense in showing you the code example, because it's literally the same two code examples as above, only in the opposite order. You start with the static method and end with the instance method.

C# developers are most likely already aware of this relationship between static methods and objects, because you can use the `this`

keyword in a static method to make it look like an instance method:

public static Bar Baz(this Foo foo, Qux qux, Corge corge)

The addition of `this`

in front of the `Foo foo`

argument enables the C# compiler to treat the `Baz`

method as though it's an instance method on a `Foo`

object:

`var bar = foo.Baz(qux, corge);`

This is only syntactic sugar. The method is still compiled as a static method, and if you, as a client developer, wish to use it as a static method, that's still possible.

### Functions #

A static method like `public static Bar Baz(Foo foo, Qux qux, Corge corge)`

looks a lot like a function. If refactored from object-oriented design, that function is likely to be impure, but its shape is function-like.

In C#, for example, you could model it as a variable of a delegate type:

Func<Foo, Qux, Corge, Bar> baz = (foo, qux, corge) => { // Do stuff, return bar };

Here, `baz`

is a function with the same signature as the above static `Baz`

method.

Have you ever noticed something odd about the various `Func`

delegates in C#?

They take the return type as the *last* type argument, which is contrary to C# syntax, where you have to declare the return type before the method name and argument list. Since C# is the dominant .NET language, that's surprising, and even counter-intuitive.

It does, however, nicely align with an ML language like F#. As we'll see in a future article, the above `baz`

function translates to an F# function with the type `Foo * Qux * Corge -> Bar`

, and to Haskell as a function with the type `(Foo, Qux, Corge) -> Bar`

. Notice that the return type comes last, just like in the C# `Func`

.

### Closures #

*...but,* you may say, *what about data with behaviour?* One of the advantages, after all, of objects is that you can associate a particular collection of data with some behaviour. The above `Foo`

class could have data members, and you may sometimes have a need for passing both data and behaviour around as a single... well... *object*.

That seems to be much harder with a static `Baz`

method.

Don't worry, write a closure:

var foo = new Foo { /* initialize members here */ }; Func<Qux, Corge, Bar> baz = (qux, corge) => { // Do stuff with foo, qux, and corge; return bar };

In this variation, `baz`

closes over `foo`

. Inside the function body, you can use `foo`

like you can use `qux`

and `corge`

. As I've already covered in an earlier article, the C# compiler compiles this to an IL class, making it even more obvious that objects and closures are two sides of the same coin.

### Summary #

Object-oriented instance methods are isomorphic to both static methods and function values. The translations that transforms your code from one to the other are *refactorings*. Since you can move in both directions without loss of information, these refactorings constitute an isomorphism.

This is another important result about the relationship between object-oriented design and functional programming, because this enables us to reduce any method to a canonical form, in the shape of a function. From a language like Haskell, we know a lot about the relationship between category theory and functional programming. With isomorphisms like the present, we can begin to extend that knowledge to object-oriented design.

**Next:** Argument list isomorphisms.

## Unit isomorphisms

*The C# and Java keyword 'void' is isomorphic to a data type called 'unit'.*

This article is part of a series of articles about software design isomorphisms.

Many programming languages, such as C# and Java, distinguish between methods that return something, and methods that don't return anything. In C# and Java, a method must be declared with a return type, but if it doesn't return anything, you can use the special keyword `void`

to indicate that this is the case:

public void Foo(int bar)

This is a C# example, but it would look similar (isomorphic?) in Java.

### Two kinds of methods #

In C# and Java, `void`

isn't a type, but a keyword. This means that there are two distinct types of methods:

- Methods that return something
- Methods that return nothing

public Foo Bar(Baz baz, Qux qux)

On the other hand, methods that return nothing must use the special `void`

keyword:

public void Bar(Baz baz, Qux qux)

If you want to generalise, you can use generics like this:

public T Foo<T, T1, T2>(T1 x, T2 y)

Such a method could return *anything*, but, surprisingly, not *nothing*. In C# and Java, *nothing* is special. You can't generalise all methods to a common set. Even with generics, you must model methods that return nothing in a different way:

public void Foo<T1, T2>(T1 x, T2 y)

In C#, for example, this leads to the distinction between Func and Action. You can't reconcile these two fundamentally distinct types of methods into one.

Visual Basic .NET makes the same distinction, but uses the keywords `Sub`

and `Function`

instead of `void`

.

Sometimes, particularly when writing code with generics, this dichotomy is really annoying. Wouldn't it be nice to be able to generalise all methods?

### Unit #

While I don't recall the source, I've read somewhere the suggestion that the keyword `void`

was chosen to go with `null`

, because *null and void* is an English (legal) idiom. That choice is, however, unfortunate.

In category theory, the term *void* denotes a type or set with *no* inhabitants (e.g. an empty set). That sounds like the same concept. The problem, from a programming perspective, is that if you have a (static) type with no inhabitants, you can't create an instance of it. See Bartosz Milewski's article Types and Functions for a great explanation and more details.

Functional programming languages like F# and Haskell instead model *nothing* by a type called *unit* (often rendered as empty brackets: `()`

). This type is a type with exactly one inhabitant, a bit like a Singleton, but with the extra restriction that the inhabitant carries no information. It simply is.

It may sound strange and counter-intuitive that a singleton value represents *nothing*, but it turns out that this is, indeed, isomorphic to C# or Java's `void`

.

This is admirably illustrated by F#, which consistently uses `unit`

instead of `void`

. F# is a multi-paradigmatic language, so you can write classes with methods as well as functions:

member this.Bar (x : int) = ()

This `Bar`

method has the return type `unit`

. When you compile F# code, it becomes Intermediate Language, which you can decompile into C#. If you do that, the above F# code becomes:

public void Bar(int x)

The inverse translation works as well. When you use F#'s interoperability features to interact with objects written in C# or Visual Basic, the F# compiler interprets `void`

methods as if they return `unit`

. For example, calling GC.Collect returns `unit`

in F#, although C# sees it as 'returning' `void`

:

> GC.Collect 0;; val it : unit = ()

F#'s `unit`

is isomorphic to C#'s `void`

keyword, but apart from that, there's nothing special about it. It's a value like any other, and can be used in generically typed functions, like the built-in `id`

function:

> id 42;; val it : int = 42 > id "foo";; val it : string = "foo" > id ();; val it : unit = ()

The built-in function `id`

simply returns its input argument. It has the type `'a -> 'a`

, and as the above F# Interactive session demonstrates, you can call it with `unit`

as well as with `int`

, `string`

, and so on.

### Monoid #

Unit, by the way, forms a monoid. This is most evident in Haskell, where this is encoded into the type. In general, a monoid is a binary operation, and not a type, but what could the combination of two `()`

(unit) values be, other than `()`

?

λ> mempty :: () () λ> mappend () () ()

In fact, the above (rhetorical) question is imprecise, since there aren't *two* unit values. There's only one, but used twice.

Since only a single *unit* value exists, any binary operation is automatically associative, because, after all, it can only return *unit*. Likewise, *unit* is the identity (`mempty`

) for the operation, because it doesn't change the output. Thus, the monoid laws hold, and *unit* forms a monoid.

This result is interesting when you start to think about composition, because a monoid can always be used to reduce (aggregate) multiple values to a single value. With this result, and unit isomorphism, we've already explained why Commands are composable.

### Summary #

Since *unit* is a type only inhabited by a single value, people (including me) often use the word *unit* about both the type and its only value. Normally, the context surrounding such use is enough to dispel any ambiguity.

*Unit* is isomorphic to C# or Java `void`

. This is an important result, because if we're to study software design and code structure, we don't have to deal with two distinct cases (methods that return nothing, and methods that return something). Instead, we can ignore methods that return nothing, because they can instead be modelled as methods that return *unit*.

The reason I've titled this article in the plural is that you could view the isomorphism between F# `unit`

and C# `void`

as a different isomorphism than the one between C# and Java `void`

. Add Haskell's `()`

(unit) type and Visual Basic's `Sub`

keyword to the mix, and it should be clear that there are many translations to the category theory concept of *Unit*.

Unit isomorphism is an example of an interlingual isomorphism, in the sense that C# `void`

maps to F# `unit`

, and vice versa. In the next example, you'll see an isomorphism that mostly stays within a single language, although a translation between languages is also pertinent.

**Next:** Function isomorphisms.

## Software design isomorphisms

*When programming, you can often express the same concept in multiple ways. If you can losslessly translate between two alternatives, it's an isomorphism. An introduction for object-oriented programmers.*

This article series is part of an even larger series of articles about the relationship between design patterns and category theory.

There's a school of functional programming that looks to category theory for inspiration, verification, abstraction, and cross-pollination of ideas. Perhaps you're put off by terms like zygohistomorphic prepromorphism (a joke), but you shouldn't be. There are often good reasons for using abstract naming. In any case, one term from category theory that occasionally makes the rounds is *isomorphism*.

### Equivalence #

Don't let the terminology daunt you. An *isomorphism* is an easy enough concept to grasp. In essence, two things are isomorphic if you can translate losslessly back and forth between them. It's a formalisation of *equivalence*.

Many programming languages, like C# and Java, offer a multitude of alternative ways to do things. Just consider this C# example from my Humane Code video:

public bool IsSatisfiedBy(Customer candidate) { bool retVal; if (candidate.TotalPurchases >= 10000) retVal = true; else retVal = false; return retVal; }

which is equivalent to this:

public bool IsSatisfiedBy(Customer candidate) { return candidate.TotalPurchases >= 10000; }

An outside observer can't tell the difference between these two implementations, because they have exactly the same externally visible behaviour. You can always refactor from one implementation to the other without loss of information. Thus, we could claim that they're isomorphic.

### Terminology #

If you're an object-oriented programmer, then you already know the word polymorphism, which sounds similar to *isomorphism*. Perhaps you've also heard the word xenomorph. It's all Greek. *Morph* means *form* or *shape*, and while *poly* means *many*, *iso* means *equal*. So *isomorphism* means 'being of equal shape'.

This is most likely the explanation for the term Isomorphic JavaScript. The people who came up with that term knew (enough) Greek, but apparently not mathematics. In mathematics, and particularly category theory, an isomorphism is a translation with an inverse. That's still not a formal definition, but just my attempt at presenting it without too much jargon.

Category theory uses the word *object* to describe a member of a category. I'm going to use that terminology here as well, but you should be aware that *object* doesn't imply object-oriented programming. It just means 'thing', 'item', 'element', 'entity', etcetera.

In category theory, a *morphism* is a mapping or translation of an object to another object. If, for all objects, there's an inverse morphism that leads back to the origin, then it's an isomorphism.

In this illustration, the blue arrows going from left to right indicate a single morphism. It's a mapping of objects on the blue left side to objects on the green right side. The green arrows going from right to left is another morphism. In this case, the green right-to-left morphism is an inverse of the blue left-to-right morphism, because by applying both morphisms, you end where you started. It doesn't matter if you start at the blue left side or the green right side.

Another way to view this is to say that a lossless translation exists. When a translation is lossless, it means that you don't lose information by performing the translation. Since all information is still present after a translation, you can go back to the original representation.

### Software design isomorphisms #

When programming, you can often solve the same problem in different ways. Sometimes, the alternatives are isomorphic: you can go back and forth between two alternatives without loss of information.

Martin Fowler's book Refactoring contains several examples. For instance, you can apply *Extract Method* followed by *Inline Method* and be back where you started.

There are many other isomorphisms in programming. Some are morphisms in the same language, as is the case with the above C# example. This is also the case with the isomorphisms in *Refactoring*, because a refactoring, by definition, is a change applied to a particular code base, be it C#, Java, Ruby, or Python.

Other programming isomorphisms go between languages, where a concept can be modelled in one way in, say, C++, but in another way in Clojure. The present blog, for instance, contains several examples of translating between C# and F#, and between F# and Haskell.

Being aware of software design isomorphisms can make you a better programmer. It'll enable you to select the best alternative for solving a particular problem. Identifying programming isomorphisms is also important because it'll enable us to formally think about code structure by reducing many alternative representations to a canonical representation. For these reasons, this article presents a catalogue of software design isomorphisms:

- Unit isomorphisms
- Function isomorphisms
- Argument list isomorphisms
- Uncurry isomorphisms
- Object isomorphisms
- Abstract class isomorphism
- Inheritance-composition isomorphism
- Tester-Doer isomorphisms
- Builder isomorphisms

*unit isomorphisms*, I mean isomorphisms to the unit value. It is, however, not an entirely consistent naming strategy.

Many more software design isomorphisms exist, so if you revisit this article in the future, I may have added more items to this catalogue. In no way should you consider this catalogue exhaustive.

### Summary #

An isomorphism is a mapping for which an inverse mapping also exists. It's a way to describe equivalence.

In programming, you often have the choice to implement a particular feature in more than one way. These alternatives may be equivalent, in which case they're isomorphic. That's one of the reasons that many code bases come with a style guide.

Understanding how code is isomorphic to other code enables us to reduce many alternatives to a canonical representation. This makes analysis easier, because we can narrow our analysis to the canonical form, and generalise from there.

**Next:** Unit isomorphisms.

## Comments

*limited to functionality*; i.e. refactoring the code may change its other aspects (readability is the first one to come to mind, performance is the second), so two different representations are no longer totally equal. Or, as another argument, using Inline Method in fact loses some information (the descriptive method name, limited variable scopes), so the translation is not (sorry) lossless.

Sergey, thank you for writing. Good point, you're right that viewed as a general-purpose translation, *Inline Method* is indeed lossy. When you look at the purpose of refactoring code, the motivation is mostly (if not always) to make the code better in some way. Particularly when the purpose is make the code more readable, a refactoring introduces clarity. Thus, going the opposite way would remove that clarity, so I think it's fair to argue that such a change would be lossy.

It's perfectly reasonable to view a refactoring like *Inline Method* as a general-purpose algorithm, in which case you're right that it's lossy. I don't dispute that.

My agenda with this article series, however, is different. I'm not trying to make multiple angels dance on a pinhead; it's not my intent to try to redefine the word *refactoring*. The purpose with this series of articles is to describe how the same behaviour can be implemented in many different ways. The book *Refactoring* is one source of such equivalent representations.

One quality of morphisms is that there can be several translations between two objects. One such translation could be the general-purpose refactoring that you so rightly point out is lossy. Another translation could be one that 'remembers' the name of the original method.

Take, as an example, the isomorphism described under the heading *Roster isomorphism* in my article Tuple monoids. When you consider the method `ToTriple`

, you could, indeed, argue that it's lossy, because it 'forgets' that the label associated with the first integer is *Girls*, that the label associated with the second integer is *Boys*, and so on. The reverse translation, however, 'remembers' that information, as you can see in the implementation of `FromTriple`

.

This isn't necessarily a 'safe' translation. You could easily write a method like this:

public static Roster FromTriple(Tuple<int, int, string[]> triple) { return new Roster(triple.Item2, triple.Item1, triple.Item3); }

This compiles, but it translates triples created by `ToTriple`

the wrong way.

On the other hand, the pair of translations that I do show in the article *is* an isomorphism. The point is that an isomorphism exists; not that it's the only possible set of morphisms.

The same argument can be applied to specific pairs of *Extract Method* and *Inline Method*. As a general-purpose algorithm, I still agree that *Inline Method* is lossy. That doesn't preclude that specific pairs of translations exist. For instance, in an article, I discuss how some people refactor Guard Clauses like this:

if (subject == null) throw new ArgumentNullException("subject");

to something like this:

Guard.AgainstNull(subject, "subject");

Again, an isomorphism exists: a translation from a Null Guard to `Guard.AgainstNull`

, and another from `Guard.AgainstNull`

to a Null Guard. Those are specific incarnations of *Extract Method* and *Inline Method*.

This may not be particularly useful as a refactoring, I admit, but that's also not the agenda of these articles. The programme is to show how particular software behaviour can be expressed in various different ways that are equivalent to each other.

## 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, semigroups, 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.

## Comments

At first, the lack of associativity felt counterintuitive: If I take equals parts of three colors, it shouldn't matter in which order I mix them. Then I realized this function doesn't take equal parts of all three. Basically the first mixture mixes one unit of each of two colors, resulting in two units of mixture. Then the second mixture takes **one** unit of the first mixture and one unit of the third color. That's why it's not associative!

Mark, thank you for writing. I never gave that question that much attention when I wrote the article, but that makes total sense. Thank you for explaining it.

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

## Comments

Is division over real numbers also a quasigroup? I think so, for any number a and b we have x and y such that:

a / x = b

y / a = b

I think division over integers is not a quasigroup since for 5 and 10 there is no x such that 5 / x = 10 since 0.5 is not an integer.

Onur, thank you for writing. In general, when pondering pure mathematics rather than their programming aspects, I'm no authority. You'd be better off researching somewhere else. The Wikipedia article on quasigroups isn't too bad for that purpose, I find.

According to that article, division of non-zero rational or real numbers is an invertible binary operation.

As far as I can tell (I'm not a mathematician) you're correct that integer division doesn't form a quasigroup. When, as you suggestion, you pick *a = 5* and *b = 10*, there's no integer *x* for which *5 / x = 10*.

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

## Comments

Thanks

Yacoub, thank you for writing. The operation used here isn't the *intersection*, but rather the *union* of 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 other BoundingBox y partially or wholly outside of the candidate.* Would that have been correct?

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!

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

## Comments

This Isomorphism applies to non-polymorphic Methods. Polymorphic Functions need to be mapped to a Set is static Methods with the same Signature. Is there a functional Construct for this?

Matt, thank you for writing. What makes you write that this isomorphism applies (only, I take it) to non-polymorphic methods. The view here is on the implementation. In C# (and all other statically typed languages that I know that support functions), functions are polymorphic based on signature.

A consumer that depends on a function with the type

`Func<Foo, Qux, Corge, Bar>`

can interact with any function with that type.