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.