Associative operation

An associative operation $\bullet : X \times X \to X$ is a binary operation such that for all $x, y, z$ in $X$, $x \bullet (y \bullet z) = (x \bullet y) \bullet z$. For example, $+$ is an associative function, because $(x + y) + z = x + (y + z)$ for all values of $x, y,$ and $z$. When an associative function is used to combine many elements in a row, parenthesis can be dropped, because the order of application is irrelevant.

Imagine that you're trying to use $f$ to combine 3 elements $x, y,$ and $z$ into one element, via two applications of $f$. $f$ is associative if $f(f(x, y), z) = f(x, f(y, z)),$ i.e., if the result is the same regardless of whether you apply $f$ to $x$ and $y$ first (and then apply that result to $z$), or whether you apply $f$ to $y$ and $z$ first (and then apply $x$ to that result).

Visualizing $f$ as a physical mechanism, there are two different ways to hook up two copies of $f$ together to create a function $f_3 : X \times X \times X \to X,$ which takes three inputs and produces one output:

An associative function $f$ is one where the result is the same no matter which way the functions are hooked up, which means that the result of using $f$ twice to turn three inputs into one output yields the same output regardless of the order in which we combine adjacent inputs.

By similar argument, an associative operator $f$ also gives rise (unambiguously) to functions $f_4, f_5, \ldots,$ meaning that associative functions can be seen as a family of functions on lists.

This justifies the omission of parenthesis when writing expressions where an associative operator $\bullet$ is applied to many inputs in turn, because the order of application does not matter. For example, multiplication is associative, so we can write expressions such as $2 \cdot 3 \cdot 4 \cdot 5$ without ambiguity. It makes no difference whether we compute the result by first multiplying 2 by 3, or 3 by 4, or 4 by 5.

By contrast, the function prependx that sticks its inputs together and puts an x on the front is not associative: prependx(prependx("a","b"),"c") = "xxabc", but prependx("a",prependx("b","c"))=xaxbc.