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:

Five ways of hooking up three instantiations of f

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.