# Generalized associative law

Given an as­so­ci­a­tive op­er­a­tor $$\cdot$$ and a list $$[a, b, c, \ldots]$$ of pa­ram­e­ters, all ways of re­duc­ing the list to a sin­gle el­e­ment by com­bin­ing ad­ja­cent pairs yield the same re­sult. In other words, while as­so­ci­a­tivity only talks about the be­hav­ior of $$f$$ when com­bin­ing three el­e­ments, this is suffi­cient to en­sure that $$f$$ has similar good be­hav­ior when com­bin­ing ar­bi­trar­ily many elements

For ex­am­ple, con­sider the list $$[a, b, c, d, e],$$ and ab­bre­vi­ate $$a \cdot b$$ as $$ab.$$ $$((ab)c)(de)$$ then de­notes the out­put cre­ated by first com­bin­ing $$a$$ and $$b$$, and then com­bin­ing that with $$c$$, and then com­bin­ing $$d$$ and $$e$$, and then putting the two re­sults to­gether.$$a(b(c(de))$$ de­notes the re­sult of com­bin­ing $$d$$ and $$e$$ first, and then com­bin­ing $$c$$ with that, and then com­bin­ing $$b$$ with that, and then com­bin­ing $$a$$ with that. The gen­er­al­ized as­so­ci­a­tive law says that all pos­si­ble or­ders of re­duc­ing the list (by com­bin­ing ad­ja­cent el­e­ments) yield the same re­sult, which means we are jus­tified in drop­ping all paren­the­sis (and just writ­ing $$abcde$$ for the re­sult of re­duc­ing the list $$[a, b, c, d, e]$$ us­ing $$\cdot$$), be­cause the or­der of ap­pli­ca­tion does not mat­ter.

Vi­su­ally, given an as­so­ci­a­tive func­tion $$f$$, there are five ways to use three copies of $$f$$ to com­bine four in­puts into one out­put:

The gen­er­al­ized as­so­ci­a­tive law says that all five yield the same re­sult. Be­cause all five com­bi­na­tions are equiv­a­lent, there is only one func­tion $$f_4$$ that uses three copies of $$f$$ to com­bine four in­puts into one out­put. Similarly, there is only one func­tion $$f_5$$ that com­bines five el­e­ments into one us­ing four ap­pli­ca­tions of $$f,$$ and so on.

# Proof sketch

As­so­ci­a­tivity of $$\cdot$$ lets us shift paren­the­sis to the left or right when ma­nipu­lat­ing ex­pres­sions that use $$\cdot$$ mul­ti­ple times in a row, be­cause as­so­ci­a­tivity says that $$(x\cdot y) \cdot z = x \cdot (y \cdot z).$$ Ab­bre­vi­at­ing $$x \cdot y$$ as $$xy,$$ we can use this rule to prove the gen­er­al­ized as­so­ci­a­tive law.

Let a “re­duc­tion path” of a list $$[a, b, c, d]$$ be an ex­pres­sion of the form $$a(b(cd)),$$ where the paren­the­sis tell us ex­plic­itly how to use ap­pli­ca­tions of $$\cdot$$ on ad­ja­cent el­e­ments to com­bine the el­e­ments of the list into a sin­gle out­put. To prove the gen­er­al­ized as­so­ci­a­tive law for lists of length 4, ob­serve that any re­duc­tion path can be turned into any other, by re­peat­edly shift­ing the paren­the­sis left or right. For ex­am­ple:

$$a(b(cd))=a((bc)d)=(a(bc))d=((ab)c)d=(ab)(cd).$$

In this case, the ex­pres­sion is trans­formed by shift­ing the in­ner paren­the­ses left, then shift­ing the outer paren­the­ses left, then shift­ing the in­ner paren­the­ses left again, then shift­ing the outer paren­the­sis right, with each step al­lowed by as­so­ci­a­tivity. By a similar method (of “walk­ing” the paren­the­sis all over the re­duc­tion path one step at a time), any two re­duc­tion paths (of the same list) can be shown equiv­a­lent.

# Implications

An as­so­ci­a­tive func­tion $$f : X \times X \to X$$ gives rise to a sin­gle nat­u­ral func­tion $$f_n$$ for re­duc­ing a list of $$n$$ in­puts to a sin­gle out­put, given any num­ber $$n \ge 1$$. ($f_1$ is the func­tion that uses zero ap­pli­ca­tions of $$f,$$ and thus leaves the in­put un­touched.) This means that we can see as­so­ci­a­tive func­tions not as just bi­nary func­tions, but as a fam­ily of func­tions for re­duc­ing lists to a sin­gle out­put.

Fur­ther­more, when­ever we want to use an as­so­ci­a­tive func­tion to re­duce a list to a sin­gle el­e­ment, we can do so in a “lo­cal” fash­ion, by re­peat­edly com­bin­ing ad­ja­cent el­e­ments in the list, with­out wor­ry­ing about the or­der in which we do so. This is cer­tainly not true for all func­tions that re­duce a list to a sin­gle out­put! For ex­am­ple, con­sider the func­tion ad­ja­cent_ones which takes a list of ones and ze­roes and pro­duces a 1 if the list con­tains any ad­ja­cent ones, and a 0 oth­er­wise. ad­ja­cent_ones(0,0,0,1,1,0)=1, but we can’t com­pute this re­sult by just com­bin­ing ad­ja­cent el­e­ments pair­wise willy-nilly: If we use the or­der ((00)(01))(10) we get the an­swer 0, when the cor­rect an­swer is 1.

As­so­ci­a­tive func­tions are pre­cisely those that give rise to a fam­ily of func­tions for re­duc­ing lists where the re­sult can be com­puted by just com­bin­ing ad­ja­cent el­e­ments pair­wise willy-nilly. Thus, as­so­ci­a­tive op­er­a­tors de­scribe list op­er­a­tions that can be com­puted lo­cally, only ever look­ing at two ad­ja­cent el­e­ments, with­out wor­ry­ing that some im­por­tant global struc­ture (such as “are there two ones in a row?”) will be de­stroyed.

This fam­ily of func­tions also has the nice prop­erty that if you re­duce one list $$[a, b, c, \ldots]$$ to a sin­gle el­e­ment $$\alpha,$$ and an­other list $$[x, y, z, \ldots]$$ to a sin­gle el­e­ment $$\chi,$$ then $$f(\alpha, \chi)$$ is the same as re­duc­ing $$[a, b, c, \ldots, x, y, z, \ldots]:$$ in other words, we can re­duce two lists sep­a­rately and then com­bine the re­sults, and get the same an­swer as we would have got­ten by com­bin­ing the lists first and then re­duc­ing them to a sin­gle re­sult.

# What about empty lists?

Any as­so­ci­a­tive func­tion $$f$$ can be used to re­duce a non-empty finite list to a sin­gle el­e­ment, by re­peat­edly ap­ply­ing $$f$$ to ad­ja­cent el­e­ments, with­out wor­ry­ing about the or­der. This works for one-el­e­ment lists, de­spite the fact that $$f$$ takes two pa­ram­e­ters, be­cause for one-el­e­ment lists we can just use zero ap­pli­ca­tions of $$f$$. But what about zero-el­e­ment lists?

To cre­ate a fam­ily $$f_n : X^n \to X$$ of func­tions on lists with the nice lo­cal­ity prop­er­ties dis­cussed above for all $$n \ge 0,$$ we need some “canon­i­cal” el­e­ment of $$0_X$$ in $$X$$ that $$f_0$$ can re­turn given an empty list, such that $$0_X$$ “acts like an empty el­e­ment” with re­spect to $$f.$$ Monoids for­mal­ize this no­tion of “an as­so­ci­a­tive op­er­a­tor plus an el­e­ment that acts like an empty el­e­ment,” and thus, they cap­ture the idea of a fam­ily of func­tions that can re­duce any list (of finite size) to a sin­gle out­put, re­gard­less of what or­der ad­ja­cent el­e­ments are com­bined in.