Typically, monoids are presented as 3-tuples (X,×,e)(X, \times, e) of a set XX equipped with an associative operation ×\times which has a two-sided identity ee. 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 (X,×,e)(X, \times, e), there is a canonical way to lift the binary operator ×\times into a function FF on lists: F:XXF([x1,,xn])=e×x1××xn \begin{align*} & F : X^\star \to X \\ & F([x_1, \dots, x_n]) = e \times x_1 \times \cdots \times x_n \end{align*} (This function is called mconcat in Haskell.) FF has the following identities with ×\times and ee: F([])=eF([a,b])=a×ba,b \begin{align*} F([]) &= e \\ F([a, b]) &= a \times b &&\forall a,b \end{align*} These identities motivate a reverse construction: given a set XX and function F:XXF : X^\star \to X, we can then define ×,e\times, e like so: e:=F([])a×b:=F([a,b]) \begin{align*} e &:= F([]) \\ a \times b &:= F([a, b]) && \end{align*} Such a construction induces a structure (X,×,e)(X, \times, e); however, this structure is not, in general, a monoid. For example: • Choosing XNX \supseteq \mathbb N and F([x1,,xn])=nF([x_1, \dots, x_n]) = n, we get e=0e = 0 and a×b=2a \times b = 2. This gives associativity on ×\times, but ee is not an identity. • Choosing XNX \supseteq \mathbb N and F([x1,,xn])=1x1+2x2++nxnF([x_1, \dots, x_n]) = 1x_1 + 2x_2 + \cdots + nx_n, we have e=0e = 0 and a×b=a+2ba \times b = a + 2b. Then ee is an identity but ×\times is not associative. The problem, then, is to find conditions on FF such that: (1) The induced (X,×,e)(X, \times, e) is guaranteed to be a monoid (2) We guarantee that F([x1,,xn])=e×x1××xnF([x_1, \dots, x_n]) = e \times x_1 \times \cdots \times x_n 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: (A) F(xyz)=F(z[F(y)]z)F(\mathbf x \oplus \mathbf y \oplus \mathbf z) = F(\mathbf z \oplus [F(\mathbf y)] \oplus \mathbf z) (Bold indicates that the symbol represents a sequence X\in X^\star rather than an element X\in X, and \oplus is sequence concatenation.) This condition gives associativity on ×\times Interpretation: when calculating F(s)F(\mathbf s), one may first calculate FF on any subsequence. (This is essentially a rephrasing of generalized associativity.) For example, with X=RX = \mathbb R and FF is summation, we equivalently have: 1+2+3+4+5=1+2+(3+4)+5F([1,2,3,4,5])=F([1,2,F([3,4]),5]) \begin{align*} 1 + 2 + 3 + 4 + 5 &= 1 + 2 + (3 + 4) + 5 \\ F([1, 2, 3, 4, 5]) &= F([1, 2, F([3, 4]), 5]) \end{align*} (B) FF is surjective This condition gives identity on ee Let us see that conditions (A) and (B) satisfy properties (1)--(4) above. Take an F:XXF : X^\star \to X satisfying (A) and (B), and let e=F([])e = F([]) and a×b=F([a,b])a \times b = F([a, b]). First note that associativity of ×\times falls out of (A): a×(b×c)=F([a,F([b,c])])=F([a][F([b,c])][])=F([a][b,c][])(A)=F([a,b,c])=F([][a,b][c])(A)=F([][F([a,b])][c])=F([F([a,b]),c])=(a×b)×c \begin{align*} & a \times (b \times c) \\ &= F([a, F([b, c])]) \\ &= F([a] \oplus [F([b, c])] \oplus []) \\ &= F([a] \oplus [b,c] \oplus []) &&(A) \\ &= F([a, b, c]) \\ &= F([] \oplus [a, b] \oplus [c]) &&(A) \\ &= F([] \oplus [F([a, b])] \oplus [c]) \\ &= F([F([a, b]), c]) \\ &= (a \times b) \times c \end{align*} The combination of (A) and (B) together give identity on ee: x×e=F([x,e])=F([x][e][])=F([x][][])(A)=F([][x][])=F([][F(x)][])where x is guaranteed by (B)=F([]x[])(A)=F(x)=x \begin{align*} & x \times e \\ &= F([x, e]) \\ &= F([x] \oplus [e] \oplus []) \\ &= F([x] \oplus [] \oplus []) &&(A) \\ &= F([] \oplus [x] \oplus []) \\ &= F([] \oplus [F(\mathbf x)] \oplus []) &&\text{where } \mathbf x \text{ is guaranteed by } (B) \\ &= F([] \oplus \mathbf x \oplus []) &&(A) \\ &= F(\mathbf x) \\ &= x \end{align*} Thus we have that (X,×,e)(X, \times, e) is a monoid, so we satisfy property (1). Now also note that: F([x]y)=F([x]y[])=F([x][F(y)][])(A)=F([x,F(y)])=x×F(y) \begin{align*} & F([x] \oplus \mathbf y) \\ &= F([x] \oplus \mathbf y \oplus []) \\ &= F([x] \oplus [F(\mathbf y)] \oplus []) &&(A) \\ &= F([x, F(\mathbf y)]) \\ &= x \times F(\mathbf y) \end{align*} Applying this inductively we get that F([x1,,xn])=x1××xn×e F([x_1, \dots, x_n]) = x_1 \times \cdots \times x_n \times e 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 (X,×,e)(X, \times, e), its induced FF satisfies (A) and (B). Generalized associativity gives (A), and for (B) we need only note that F([a])=aF([a]) = a and thus FF is surjective. === Post-script === If we have an F:XXF : X^\star \to X 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. ×\times is associative 2. x×e=F([x])x \times e = F([x]) 3. F([x1,,xn])=x1××xn×eF([x_1, \dots, x_n]) = x_1 \times \cdots \times x_n \times e This is close, but we are missing that F([a])=aF([a]) = a, 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 FF form a magma homomorphism (X,)(X,×)(X^\star, \oplus) \to (X, \times); i.e., F(xy)=F(x)×F(y) F(\mathbf x \oplus \mathbf y) = F(\mathbf x) \times F(\mathbf y) Call this condition (M). Interestingly, (M) is not as strong as we would like. If we ask for FF to satisfy (M) and (B) rather than (A) and (B), we get that: 1. ×\times is associative (x×y)×z=(F(x)×F(y))×F(z)(B)=F(xy)×F(z)(M)=F((xy)z)(M)=F(x(yz))=F(x)×(F(y)×F(z))(M)=x×(y×z) \begin{align*} & (x\times y)\times z \\ &= (F(\mathbf x) \times F(\mathbf y)) \times F(\mathbf z) &&(B) \\ &= F(\mathbf x \oplus \mathbf y)\times F(\mathbf z) &&(M) \\ &= F((\mathbf x \oplus \mathbf y) \oplus \mathbf z) &&(M) \\ &= F(\mathbf x \oplus (\mathbf y \oplus \mathbf z)) \\ &= F(\mathbf x)\times (F(\mathbf y) \times F(\mathbf z)) &&(M) \\ &= x\times (y\times z) \end{align*} 2. ee is a two-sided identity x×e=F(x)×e(B)=F(x)×F([])=F(x[])(M)=F(x)=x \begin{align*} & x \times e \\ &= F(\mathbf x) \times e &&(B) \\ &= F(\mathbf x) \times F([]) \\ &= F(\mathbf x \oplus []) &&(M) \\ &= F(\mathbf x) \\ &= x \end{align*} Thus we get that inducing (X,×,e)(X, \times, e) from FF produces a monoid; however, it might actually not be the monoid we had in mind. The strongest we can get is: 3. F([x1,,xn])={x1××xn2nx1××xn1×F([xn])2n F([x_1, \dots, x_n]) = \begin{cases} x_1 \times \cdots \times x_n & 2 \mid n \\ x_1 \times \cdots \times x_{n-1} \times F([x_n]) & 2 \nmid n \end{cases} Illustrative example: F([q,r,s,t,u])=F([q,r][s,t][u])=F([q,r])×F([s,t])×F([u])(M)=(q×r)×(s×t)×F([u])=q×r×s×t×F([u]) \begin{align*} & F([q, r, s, t, u]) \\ &= F([q, r] \oplus [s, t] \oplus [u]) \\ &= F([q, r]) \times F([s, t]) \times F([u]) &&(M) \\ &= (q \times r) \times (s \times t) \times F([u]) \\ &= q \times r \times s \times t \times F([u]) \end{align*} I believe that this somewhat-bizarre result essentially boils down to the fact that e=F([])e = F([]) is defined in terms of the length-0 list [][] and a×b:=F([a,b])a \times b := F([a, b]) is defined in terms of the length-2 list [a,b][a, b], so how FF acts on lists of non-even length is irrelevant to the monoid (X,×,e)(X, \times, e). What we are missing is that F([a])=aF([a]) = a, and this is not guaranteed by (M) and (B). Counter-example (thanks to Mason Mackaman for helping me find this!): Take X=Z/2X = \mathbb Z / 2 and define F([x1,,xn])=x1++xn+nF([x_1, \dots, x_n]) = x_1 + \cdots + x_n + n. Then: FF satisfies (M): F([x1,,xk][xk+1,,xn])=F([x1,,xn])=(x1+xn)+n=(x1++xk+xk+1+xn)+(k+(nk))=(x1++xk+k)+(xk+1++xn+(nk))=F([x1,,xk])+F([xk+1,,xn]) \begin{align*} & F([x_1, \dots, x_k] \oplus [x_{k+1}, \dots, x_n]) \\ &= F([x_1, \dots, x_n]) \\ &= (x_1 + \cdots x_n) + n \\ &= (x_1 + \cdots + x_k + x_{k+1} + \cdots x_n) + (k + (n-k)) \\ &= (x_1 + \cdots + x_k + k) + (x_{k+1} + \cdots + x_n + (n-k)) \\ &= F([x_1, \dots, x_k]) + F([x_{k+1}, \dots, x_n]) \end{align*} FF satisfies (B), since F([x,0])=x+0=xF([x, 0]) = x + 0 = x FF does not satisfy F([a])=aF([a]) = a: we have F([x])=x+1xF([x]) = x + 1 \neq x! #onwards Referenced by: