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.