Associativity vs commutativity

Associativity and commutativity are often confused, because they are both constraints on how a function treats its inputs, and they are both constraints saying “these two paths for calculating the output must yield the same answer.” The difference is that commutativity says “this function shouldn’t care what order its own arguments come in,” while associativity says “different ways of using this function multiple times should yield the same results.”

Commutativity is about an invariance in one call to the function: If you run the function once with inputs \(x\) and \(y,\) you’ll get the same result as if you run it once with inputs \(y\) and \(x.\)

Associativity is about an invariance in multiple calls to the function: If you combine four elements using three function calls in the order \(a \cdot (b \cdot (c \cdot d)),\) you’ll get the same answer as if you use the three function calls in the order \(((a \cdot b) \cdot c) \cdot d.\)

Commutativity means you can swap the order of the elements. Associativity means you can drop parenthesis when combining multiple elements in a row.

If an operator \(\cdot\) is both commutative and associative, then when you’re combining multiple elements in a row, you’re welcome to combine them in any order: For example, when adding \(3 + 2 + (-7) + 5 + (-2) + (-3) + 7,\) we can re-arrange the list to get \(3 - 3 + 2 - 2 + 7 - 7 + 5 = 5,\) which makes calculation easy. To see that this is the case, note that the result won’t change if we swap any two adjacent elements, because associativity means that we can pick any two adjacent elements to start with and commutativity says that the order of those elements doesn’t matter. Then, we can re-arrange the list however we like using a series of two-element swaps. Perhaps conditionalize this parenthetical on something like “cares about abstract algebra” or “wants tidbits they don’t understand to point them towards cool things” or something. (This is why commutative groups are especially easy to work with.)

Examples

Addition is both commutative and associative (same with multiplication). Subtraction is neither commutative nor associative (same with division).

String concatenation is associative but not commutative: If you’re sticking a bunch of strings together end on end, then it doesn’t matter which adjacent pairs you combine first, but "onetwo" is a very different string than "twoone".

Rock-paper-scissors is commutative but not associative. The winner of “rock v scissors” is rock, and the winner of “scissors v rock” is rock, and so on; but if you have a bunch of people in a line make rock, paper, or scissors signs, then who is the winer depends on which end of the line you start from: If the line has three people, and they throw paper, scissors, then the winner will be whoever threw scissors if you start from the left (by finding the winner between rock and paper, and then playing that against scissors) or rock if you start on the right (by finding the winner between paper and scissors, and then playing that against rock).

The function pair which puts its inputs into a pair (such that pair(x, y) = (x, y)) is neither commutative nor associative: (x, y) does not equal (y, x), and (x, (y, z)) does not equal ((x, y), z). The output of pair preserves the ordering and structure of all its inputs, and leaves a trace that allows one to distinguish which inputs it was called on when. Both commutativity and associativity require the function to be “forgetful” about some aspect of how it was called: Commutative functions need to be insensitive to the ordering of their arguments; associative functions need to leave no trace that can be used to figure out which inputs were combined in what order. Thus, any function that bakes a lot of history about what it was called with into the output is unlikely to be commutative or associative.

Mnemonics

If it helps you to remember which is which, consider these two mnemonics:

For “commutativity,” imagine that the two parameters to the function each live on one side of town and work on the other side. Each morning, they pass each other on their morning commute, as they swap places.

For “associativity,” imagine a bunch of associates all standing in a line, ranked according to their hierarchy in a law firm. Any two adjacent people are willing to converse with each other, although people on one end of the line might not be willing to associate with people on the other end.