Editing Monoid (section)

== MapReduce ==
An application of monoids in computer science is the so-called [[MapReduce]] programming model (see [https://erikerlandson.github.io/blog/2016/09/05/expressing-map-reduce-as-a-left-folding-monoid/ Encoding Map-Reduce As A Monoid With Left Folding]). MapReduce, in computing, consists of two or three operations. Given a dataset, "Map" consists of mapping arbitrary data to elements of a specific monoid. "Reduce" consists of folding those elements, so that in the end we produce just one element.

For example, if we have a [[multiset]], in a program it is represented as a map from elements to their numbers. Elements are called keys in this case. The number of distinct keys may be too big, and in this case, the [[multiset]] is being sharded. To finalize reduction properly, the "Shuffling" stage regroups the data among the nodes. If we do not need this step, the whole Map/Reduce consists of mapping and reducing; both operations are parallelizable, the former due to its element-wise nature, the latter due to associativity of the monoid.