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)
“May we not assure ourselves that whatever woman’s thought and study shall embrace will thereby receive a new inspiration, that she will save science from materialism, and art from a gross realism; that the “eternal womanly shall lead upward and onward”?”
—Louisa Parsons Hopkins, U.S. scientist and author. As quoted in The Fair Women, ch. 16, by Jeanne Madeline Weimann (1981)