- string concatenation is a monoid, with the empty string as the identity element. In fact, string concatenation is the most general monoid on a set, called the "free monoid"; all other monoids can be made from it by defining a canonicalization operation. For integer addition, for example, you can collapse a string of integers such as [4, -1, 2] down to their sum, such as . Note that the free monoid is not commutative, and although it is invertible (in "hairy" || " and a half" = "hairy and a half", you can take " and a half" off and get the original "hairy"), it doesn't have inverse elements.
- max and min on a closed set, and more generally all semilattices. Let's write 4 \/ 5 = 5 \/ 4 = 5. This \/ is associative and has an identity (whatever the maximum of the closed set is; we can augment the integers with -∞ and +∞ and use -∞ as the identity element), so it forms a monoid. Any theorem about monoids will work equally well for string concatenation and for this pairwise max operator. Isn't that wild?
- & and | for bitstrings of some length. This is also a lattice.
- Matrix multiplication (for matrices of a particular square shape).
- The morphological dilation operation.
It turns out that they actually form a much richer structure called a ring when you add in their addition operator as well: https://en.m.wikipedia.org/wiki/Matrix_ring
For example, stacks of paper can be thought of as a monoid. Given two stacks, you can stack one on top of the other (the top and bottom of the stack standing in for the ports). The vacuous concept of a stack of zero sheets of paper is the "empty" object.
Another example is the set of PNG files. There are a number of monoids you could define, like horizontal concatenation of images, or the vertical concatenation of images. A non-example is blending two images with 50% opacity each, since depending on the order you blend the images, like (AB)C versus A(BC), image A might contribute 25% or 50% to the final image.
For some monoids, the left/right port distinction doesn't matter. Consider buckets of marbles. The way you join two buckets of marbles is to dump them into a single bucket. The empty bucket is the empty object. It doesn't matter in which order you dump the marbles into a bucket --- you'll get the same number of marbles in the end.
This mostly makes sense, although... not for arrays where order matters...?
The second kind is joining things through time, where it is not supposed to matter when you join things. If you have three stacks of paper, you can stack the first onto the second and put that on the third, or you can stack the second on the third and put the first on top of that, and you get essentially the same pile in either case.
Piles are supposed to be an analogue of arrays, where the first kind of order matters.
Lots of times, the second kind of order (associativity) actually does matter, too, where you get literally different objects, but it's ok since there are "equal" in a useful sense. For example, when you make a text editor, you might use the rope data structure to represent strings. If so, when you concatenate a list of strings, the literal tree structures you get in the representation of the rope might vary depending how you did it, but they'll all be equal in the sense that the strings they represent are equal --- the same characters in the same order.
(a • b) • c == a • (b • c)
a • b == b • a
you'll notice that associativity indeed holds for strings (or arrays of some T), where concatenation is the monoidal operation:
("he" ++ "ll") ++ "o!" ==
"he ++ ("ll" ++ "o!") ==
as = [a0, a1, a2, ..., an-1, an]
r = (a0 • a1 • a2 • ... • an)
r0 = (a0•a1•a2) // worker 0
r1 = (a3•a4•a5) // worker 1
rm = (an-2,an-1,an) // worker m
r = r0•r1•...•rm // sum up what the workers produced
btw, an example of a less trivial monoid is `sorted lists of T `:
- `•`, the monoidal operation, is `merge(a, b)`, which combines two sorted lists into a new sorted list: `merge([1,2,3,5], [2,4]) == [1,2,2,3,4,5]`
- `e`, the "neutral element", is just the empty list ``
this is a (commutative) monoid, and you could say that mergesort relies on its monoidal properties to work!
¹ if you can swap values around and still get the same result, you've got a "commutative monoid".
rm = (an-2•an-1•an)
x * 1 = x
1 * x = 1
x * (y * z) = (x * y) * z
Now consider the following equations for strings:
concat(x, "") = x
concat("", x) = x
concat(x, concat(y, z)) = concat(concat(x, y), z)
Now consider the following equations for booleans:
x or false = x
false or x = x
x or (y or z) = (x or y) or z
If you can see the pattern, you understand monoids. Monoids are everywhere in programming.
Alright, first thing I noticed was the presence of identity operators.
But then you're replacing the identity "operator" with an expression. Combining this with some of what other people are saying, and one aspect of monoids is that they're... chainable? The value of a monoid expression is the same type as the parameters of the monoid expression; `bar someMonoidFunction(bar x, bar y)`...?
This then has some interesting ramifications for chaining/composing, as you demonstrate in the third example of each group.
There's... something further than this, I can tell, but it's not yet clear to me.
Can you do one these wonderful - heh, koans, basically - for something like `sin(cos(x))`?
It's 'chainable', or the more precise mathematical term is "closed". It has a value that can be used as an identity. And it's associative. Where associative means that when 'chaining' multiple operations (as you termed it) it doesn't matter how you group with parentheses; it'll produce the same result.
The identity function I(x)=x is the identity: f ∘ I = f = I ∘ f.
Monoids are very abstract which means they only have the vaguest kind of sort of like addition on them. Groups are less abstract, semigroups more abstract.
To be sort of like addition up to the level of monoids, you having to:
1. have something that's a bit like 0
2. adding in a random parenthesis doesn't matter
3. it needs to be an operation on two elements, like two strings, two logical values, or two numbers
That's it really. Sometimes you have to squint at an operation to see how it's like addition. Which is to say it's not really about addition at all. It's just an operation. It's about the specific three rules.