About Monoids

In mathematics, we have this universal model that we mathematicians call Sets. The study of Sets is known as Set Theory. It would seem that a Thing is a more universal quantity than a Set. But in mathematics we tend to construct operations that are applicable to the entire classes of Things rather than singular Things. So we group these things into Sets. For example, a mouse is a Thing:

mouse: Thing

But the abstract operation "catch a mouse" should be able to catch any mouse. Let's try to type this:

catchAMouse: Thing → Caught<Thing>

This may seem alright, but for a mathematician catchAMouse's domain (the left side of →) is too wide because it may catch anything (any: Thing). Let's instead introduce a confusingly named set Mouse that contains all mice:

Mouse := { mousefirst, mousesecond, ..., mouselast }

Now if we assume:

*: Mouse iff * ∈ Mouse

then we can craft a better-looking mouse-catching operation:

betterCatchAMouse: Mouse → Caught<Mouse>

betterCatchAMouse(mousefirst) = Caught(mousefirst)

cat: Cat
betterCatchAMouse(cat) -- does not compute, cat is not a Mouse

So Thing should naturally mean Set of all Things. You are a Thing if and only if you belong to the Set of all Things, which you must. You are a Mouse if and only if you belong to the Set of all Mice, which you may. Sets are kinda types, Things are kinda instances of types. Sets exist to promote generalization. It's convenient.

With sets, we can even conceptualize nothingness:

Thing+ = { something, nothing }

We know that nothing from nothing leaves nothing. You gotta have something if you wanna be with me. Let's formalize this intuition in an addition operation over Thing+:

+: Thing+ × Thing+ → Thing+
nothing + nothing := nothing
nothing + something := something
something + nothing := something
something + something := something

Did we accidentally invent boolean OR? Likely. But we also accidentally invented a Monoid.

Any Set is a Monoid if it has a nothing in it:

monoid: Set = { somethingfirst, ... somethinglast, nothing }

You are truly nothing if combining you with an x yields an x. So a Set is truly a Monoid if it has a combining operation (+) such that:

nothing (+) nothing := nothing
x (+) nothing := x
nothing (+) y := y
x (+) y := actuallyCombine(x, y)

Now here's the surprising part. Why do you think Monoids are called Monoids? Because a Monoid is actually a Category with a single (mono) Object (+); xs and ys in such a Category are considered Morphisms, so in category theoretic sense actuallyCombine = ○ and nothing is an identity Morphism:

id (+) id = id
id (+) f = f
f (+) id = f
id (+) g := g
f (+) g := f ○ g

So why am I even talking about this? Well, first of all, this was very unexpected for me. I learned this from the book Category Theory for Computer Science I know I told you I was a mathematician, but I'm really a computer scientist in disguise, so I have to read this kind of books to under any maths.

The surprising part is thingink about Quantities as Morphisms rather than Objects and an Operator as an Object rather than a Morphism. Very counter-intuitve.

The other thing is that Monoids are quite fundamental. When you think of a nothing as a Morphism, it sounds more like do nothing than be nothing. Monoids are an abstraction for Processes, or maybe Processes are manifestations of Monoids. Many Actions of a Process are the Morphisms, and the singular (mono) Operation of a Process is Connection: a way to say that this Action goes after this Action. For parallel Actions we have Symmetric Monoids, a special kind of Monoid with a tensor product ⊗ operation for parallel composition. I'm not even making this up, this is what people actually do and they seem to like it.

Monoids is pretty high up in the hierarchy of common categories. It goes something like this: Group ← Monoid ← Semigroup ← Magma. Groups, unlike Monoids, have to have an inverse element, which is not that common in nature. I'd say a Group is a kind of balanced Monoid, where the Unit is the middle point, not the beginning (or ending, if you think that end is more correct than beginning). The nothingness, unlike the balanced center, is ubiquitous.

In conclusion, there's something pretty cool about Monoids and you must love them.