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:
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)
“The puritanical potentialities of science have never been forecast. If it evolves a body of organized rites, and is established as a religion, hierarchically organized, things more than anything else will be done in the name of “decency.” The coarse fumes of tobacco and liquors, the consequent tainting of the breath and staining of white fingers and teeth, which is so offensive to many women, will be the first things attended to.”
—Wyndham Lewis (1882–1957)