Free Monoids and Computing
The free monoid on a set A corresponds to lists of elements from A with concatenation as the binary operation. A monoid homomorphism from the free monoid to any other monoid (M,•) is a function f such that
- f(x1…xn) = f(x1) • … • f(xn)
- f = e
where e is the identity on M. Computationally, every such homomorphism corresponds to a map operation applying f to all the elements of a list, followed by a fold operation which combines the results using the binary operator •. This computational paradigm (which can be generalised to non-associative binary operators) has inspired the MapReduce software framework.
Read more about this topic: Free Monoid
Famous quotes containing the word free:
“Opinions are not to be learned by rote, like the letters of an alphabet, or the words of a dictionary. They are conclusions to be formed, and formed by each individual in the sacred and free citadel of the mind, and there enshrined beyond the arm of law to reach, or force to shake; ay! and beyond the right of impertinent curiosity to violate, or presumptuous arrogance to threaten.”
—Frances Wright (1795–1852)