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 well-educated young woman of 1950 will blend art and sciences in a way we do not dream of; the science will steady the art and the art will give charm to the science. This young woman will marry—yes, indeed, but she will take her pick of men, who will by that time have begun to realize what sort of men it behooves them to be.”
—Ellen Henrietta Swallow Richards (1842–1911)