A monoid is a combination of a set and an operation and an identity element. In
programming, a set is a data type (like a
DateTime). A monoid is a subset
of a semigroup, it is more strict than the latter. A monoid has the following
operation must be binary - it acts on two inputs (e.g. addition, or a function
(Car, Car) => Car). Notice that the type of inputs and the output is the same. That’s because a Monoid is a combinaton of a single data type and an operation.
it must be associative - e.g.,
(1 + 2) + 3 = 1 + (2 + 3)- order of evaluation does not matter, the result is the same.
there’s a neutral element, sometimes also called the identity element - it’s a value that is neutral in a sense that it does not incur any change, it does nothing when an operation is applied to it. An example of an identity element in the addition operation is
a + 0 = a. For multiplication, the identity element is
a * 1 = a.
A monoid could also be described as a triplet consisiting of:
- a set
- a binary operation
- an identity element
The above triplet must satisfy the aforementioned rules.
- Addition on numbers, 0 is the identity
- Multiplication on numbers, 1 is the identity
- AND on boolean numbers, 1 is the identity
- OR on boolean numbers, 0 is the identity
- Concatenation on a collection, empty collection is the identity
Note that a tuple (also triple, quadriple, and so on…) may also be a monoid. It will be one only if all of its elements are monoids. The same goes for types, like a C# record. A C# record is a monoid if and only if all of its properties form a monoid when combined with some operation and identity element.
In the example abovr,
SingingRobots are integers. They
form monoids with addition and 0 as an identity element. In case of
DischargedRobots, the concatenation operation and an empty list form a monoid.
We may define the following operation on
And here’s the identity:
Any function that returns a monoid is itself a monoid. The input parameters do not matter.
An example could be the following TypeScript signature:
number forms a monoid under addition, and 0 identity element.
string, as a collection, also does form a monoid, however, it doesn’t have to
for the function to form a monoid.
Here’s some functions that follow the signature:
Here’s the identity element
The operation to form a monoid:
So far, we’ve been discussing functions that accept two arguments - binary functions. Endomorphisms are simpler - these are unary functions that return the same type as they accept as an argument. Here’s an example:
A quote from Mark Seemann’s article:
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.
More precisely, the composition forms a function that forms a monoid, since there will be an identity element (function), and associativity requirement will be fulfilled.
Having a collection of values that are part of some monoid’s set, we can accumulate them into one value. Such an operation is called Reduce or Fold in functional programming.
.NET has a built-in implementation of accumulation -