Editing Monoid (section)

== Monoids in computer science ==
In computer science, many [[abstract data types]] can be endowed with a monoid structure. In a common pattern, a [[sequence]] of elements of a monoid is "[[fold (higher-order function)|folded]]" or "accumulated" to produce a final value. For instance, many iterative algorithms need to update some kind of "running total" at each iteration; this pattern may be elegantly expressed by a monoid operation. Alternatively, the associativity of monoid operations ensures that the operation can be [[parallelization|parallelized]] by employing a [[prefix sum]] or similar algorithm, in order to utilize multiple cores or processors efficiently.

Given a sequence of values of type {{math|''M''}} with identity element {{math|''ε''}} and associative operation&nbsp;{{math|•}}, the ''fold'' operation is defined as follows:
: <math>\mathrm{fold}: M^{*} \rarr M = \ell \mapsto \begin{cases} \varepsilon & \mbox{if } \ell = \mathrm{nil} \\ m \bullet \mathrm{fold} \, \ell' & \mbox{if } \ell = \mathrm{cons} \, m \, \ell' \end{cases}</math>

In addition, any [[data structure]] can be 'folded' in a similar way, given a serialization of its elements. For instance, the result of "folding" a [[binary tree]] might differ depending on pre-order vs. post-order [[tree traversal]].