Associative operation

An as­so­ci­a­tive op­er­a­tion \(\bullet : X \times X \to X\) is a bi­nary op­er­a­tion such that for all \(x, y, z\) in \(X\), \(x \bullet (y \bullet z) = (x \bullet y) \bullet z\). For ex­am­ple, \(+\) is an as­so­ci­a­tive func­tion, be­cause \((x + y) + z = x + (y + z)\) for all val­ues of \(x, y,\) and \(z\). When an as­so­ci­a­tive func­tion is used to com­bine many el­e­ments in a row, paren­the­sis can be dropped, be­cause the or­der of ap­pli­ca­tion is ir­rele­vant.

Imag­ine that you’re try­ing to use \(f\) to com­bine 3 el­e­ments \(x, y,\) and \(z\) into one el­e­ment, via two ap­pli­ca­tions of \(f\). \(f\) is as­so­ci­a­tive if \(f(f(x, y), z) = f(x, f(y, z)),\) i.e., if the re­sult is the same re­gard­less of whether you ap­ply \(f\) to \(x\) and \(y\) first (and then ap­ply that re­sult to \(z\)), or whether you ap­ply \(f\) to \(y\) and \(z\) first (and then ap­ply \(x\) to that re­sult).

Vi­su­al­iz­ing \(f\) as a phys­i­cal mechanism, there are two differ­ent ways to hook up two copies of \(f\) to­gether to cre­ate a func­tion \(f_3 : X \times X \times X \to X,\) which takes three in­puts and pro­duces one out­put:

Two ways of combining f

An as­so­ci­a­tive func­tion \(f\) is one where the re­sult is the same no mat­ter which way the func­tions are hooked up, which means that the re­sult of us­ing \(f\) twice to turn three in­puts into one out­put yields the same out­put re­gard­less of the or­der in which we com­bine ad­ja­cent in­puts.

3-arity f

By similar ar­gu­ment, an as­so­ci­a­tive op­er­a­tor \(f\) also gives rise (un­am­bigu­ously) to func­tions \(f_4, f_5, \ldots,\) mean­ing that as­so­ci­a­tive func­tions can be seen as a fam­ily of func­tions on lists.

This jus­tifies the omis­sion of paren­the­sis when writ­ing ex­pres­sions where an as­so­ci­a­tive op­er­a­tor \(\bullet\) is ap­plied to many in­puts in turn, be­cause the or­der of ap­pli­ca­tion does not mat­ter. For ex­am­ple, mul­ti­pli­ca­tion is as­so­ci­a­tive, so we can write ex­pres­sions such as \(2 \cdot 3 \cdot 4 \cdot 5\) with­out am­bi­guity. It makes no differ­ence whether we com­pute the re­sult by first mul­ti­ply­ing 2 by 3, or 3 by 4, or 4 by 5.

By con­trast, the func­tion prependx that sticks its in­puts to­gether and puts an x on the front is not as­so­ci­a­tive: prependx(prependx("a","b"),"c") = "xxabc", but prependx("a",prependx("b","c"))=xaxbc.



  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.