Associativity vs commutativity

As­so­ci­a­tivity and com­mu­ta­tivity are of­ten con­fused, be­cause they are both con­straints on how a func­tion treats its in­puts, and they are both con­straints say­ing “these two paths for calcu­lat­ing the out­put must yield the same an­swer.” The differ­ence is that com­mu­ta­tivity says “this func­tion shouldn’t care what or­der its own ar­gu­ments come in,” while as­so­ci­a­tivity says “differ­ent ways of us­ing this func­tion mul­ti­ple times should yield the same re­sults.”

Com­mu­ta­tivity is about an in­var­i­ance in one call to the func­tion: If you run the func­tion once with in­puts \(x\) and \(y,\) you’ll get the same re­sult as if you run it once with in­puts \(y\) and \(x.\)

As­so­ci­a­tivity is about an in­var­i­ance in mul­ti­ple calls to the func­tion: If you com­bine four el­e­ments us­ing three func­tion calls in the or­der \(a \cdot (b \cdot (c \cdot d)),\) you’ll get the same an­swer as if you use the three func­tion calls in the or­der \(((a \cdot b) \cdot c) \cdot d.\)

Com­mu­ta­tivity means you can swap the or­der of the el­e­ments. As­so­ci­a­tivity means you can drop paren­the­sis when com­bin­ing mul­ti­ple el­e­ments in a row.

If an op­er­a­tor \(\cdot\) is both com­mu­ta­tive and as­so­ci­a­tive, then when you’re com­bin­ing mul­ti­ple el­e­ments in a row, you’re wel­come to com­bine them in any or­der: For ex­am­ple, when adding \(3 + 2 + (-7) + 5 + (-2) + (-3) + 7,\) we can re-ar­range the list to get \(3 - 3 + 2 - 2 + 7 - 7 + 5 = 5,\) which makes calcu­la­tion easy. To see that this is the case, note that the re­sult won’t change if we swap any two ad­ja­cent el­e­ments, be­cause as­so­ci­a­tivity means that we can pick any two ad­ja­cent el­e­ments to start with and com­mu­ta­tivity says that the or­der of those el­e­ments doesn’t mat­ter. Then, we can re-ar­range the list how­ever we like us­ing a se­ries of two-el­e­ment swaps. Per­haps con­di­tion­al­ize this par­en­thet­i­cal on some­thing like “cares about ab­stract alge­bra” or “wants tid­bits they don’t un­der­stand to point them to­wards cool things” or some­thing. (This is why com­mu­ta­tive groups are es­pe­cially easy to work with.)

Examples

Ad­di­tion is both com­mu­ta­tive and as­so­ci­a­tive (same with mul­ti­pli­ca­tion). Sub­trac­tion is nei­ther com­mu­ta­tive nor as­so­ci­a­tive (same with di­vi­sion).

String con­cate­na­tion is as­so­ci­a­tive but not com­mu­ta­tive: If you’re stick­ing a bunch of strings to­gether end on end, then it doesn’t mat­ter which ad­ja­cent pairs you com­bine first, but “onetwo” is a very differ­ent string than “twoone”.

Rock-pa­per-scis­sors is com­mu­ta­tive but not as­so­ci­a­tive. The win­ner of “rock v scis­sors” is rock, and the win­ner of “scis­sors v rock” is rock, and so on; but if you have a bunch of peo­ple in a line make rock, pa­per, or scis­sors signs, then who is the winer de­pends on which end of the line you start from: If the line has three peo­ple, and they throw pa­per, scis­sors, then the win­ner will be who­ever threw scis­sors if you start from the left (by find­ing the win­ner be­tween rock and pa­per, and then play­ing that against scis­sors) or rock if you start on the right (by find­ing the win­ner be­tween pa­per and scis­sors, and then play­ing that against rock).

The func­tion pair which puts its in­puts into a pair (such that pair(x, y) = (x, y)) is nei­ther com­mu­ta­tive nor as­so­ci­a­tive: (x, y) does not equal (y, x), and (x, (y, z)) does not equal ((x, y), z). The out­put of pair pre­serves the or­der­ing and struc­ture of all its in­puts, and leaves a trace that al­lows one to dis­t­in­guish which in­puts it was called on when. Both com­mu­ta­tivity and as­so­ci­a­tivity re­quire the func­tion to be “for­get­ful” about some as­pect of how it was called: Com­mu­ta­tive func­tions need to be in­sen­si­tive to the or­der­ing of their ar­gu­ments; as­so­ci­a­tive func­tions need to leave no trace that can be used to figure out which in­puts were com­bined in what or­der. Thus, any func­tion that bakes a lot of his­tory about what it was called with into the out­put is un­likely to be com­mu­ta­tive or as­so­ci­a­tive.

Mnemonics

If it helps you to re­mem­ber which is which, con­sider these two mnemon­ics:

For “com­mu­ta­tivity,” imag­ine that the two pa­ram­e­ters to the func­tion each live on one side of town and work on the other side. Each morn­ing, they pass each other on their morn­ing com­mute, as they swap places.

For “as­so­ci­a­tivity,” imag­ine a bunch of as­so­ci­ates all stand­ing in a line, ranked ac­cord­ing to their hi­er­ar­chy in a law firm. Any two ad­ja­cent peo­ple are will­ing to con­verse with each other, al­though peo­ple on one end of the line might not be will­ing to as­so­ci­ate with peo­ple on the other end.