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 "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 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 M with identity element and associative operation, the fold operation is defined as follows:
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.
Read more about this topic: Monoid
Famous quotes containing the words computer and/or science:
“Family life is not a computer program that runs on its own; it needs continual input from everyone.”
—Neil Kurshan (20th century)
“I exulted like “a pagan suckled in a creed” that had never been worn at all, but was brand-new, and adequate to the occasion. I let science slide, and rejoiced in that light as if it had been a fellow creature. I saw that it was excellent, and was very glad to know that it was so cheap. A scientific explanation, as it is called, would have been altogether out of place there. That is for pale daylight.”
—Henry David Thoreau (1817–1862)