Typically, monoids are presented as 3-tuples of a set equipped with an associative operation which has a two-sided identity .
This presentation works fine, but has always striked me as somewhat opaque: what does it mean? To me, the essential defining feature of a monoid is its relation with lists. So I offer the following re-presentation of the concept of a monoid which promotes lists to a first-class discussion topic.
First, let us note that given a monoid , there is a canonical way to lift the binary operator into a function on lists:
(This function is called
mconcat in Haskell.) has the following identities with and :
These identities motivate a reverse construction: given a set and function , we can then define like so:
Such a construction induces a structure ; however, this structure is not, in general, a monoid. For example:
• Choosing and , we get and . This gives associativity on , but is not an identity.
• Choosing and , we have and . Then is an identity but is not associative.
The problem, then, is to find conditions on such that:
(1) The induced is guaranteed to be a monoid
(2) We guarantee that
That is, we induce "the right" monoid
(Somewhat surprisingly, this condition doesn't follow from (1). More on this later.)
(3) The conditions feel a little bit more meaningful/evocative than assocativity and identity
(4) The conditions are necessary (as well as sufficient)
I offer the following conditions:
(Bold indicates that the symbol represents a sequence rather than an element , and is sequence concatenation.)
This condition gives associativity on
Interpretation: when calculating , one may first calculate on any subsequence. (This is essentially a rephrasing of generalized associativity.) For example, with and is summation, we equivalently have:
(B) is surjective
This condition gives identity on
Let us see that conditions (A) and (B) satisfy properties (1)--(4) above.
Take an satisfying (A) and (B), and let and .
First note that associativity of falls out of (A):
The combination of (A) and (B) together give identity on :
Thus we have that is a monoid, so we satisfy property (1).
Now also note that:
Applying this inductively we get that
meaning we satisfy property (2).
I will skip over property (3), as it is rather subjective, but say that, at the very least, I find conditions (A) and (B) to be somewhat evocative. (That's why I went about discovering them, after all.)
Finally, property (4), that given a monoid , its induced satisfies (A) and (B). Generalized associativity gives (A), and for (B) we need only note that and thus is surjective.
=== Post-script ===
If we have an which satisfies (A) but not (B), we can do most of the proof given above, but end up stuck. In particular, our results are that:
1. is associative
This is close, but we are missing that , which I conjecture to be equivalent to surjectivity when given (A). (Probably not hard to prove this one way or another, but I don't want to at the moment)
=== Post-script ===
A similar condition to (A) is to ask that form a magma homomorphism ; i.e.,
Call this condition (M).
Interestingly, (M) is not as strong as we would like. If we ask for to satisfy (M) and (B) rather than (A) and (B), we get that:
1. is associative
2. is a two-sided identity
Thus we get that inducing from produces a monoid; however, it might actually not be the monoid we had in mind. The strongest we can get is:
I believe that this somewhat-bizarre result essentially boils down to the fact that is defined in terms of the length-0 list and is defined in terms of the length-2 list , so how acts on lists of non-even length is irrelevant to the monoid .
What we are missing is that , and this is not guaranteed by (M) and (B). Counter-example (thanks to Mason Mackaman for helping me find this!): Take and define . Then:
satisfies (B), since
does not satisfy : we have !