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:
“The mere fact of leaving ultimate social control in the hands of the people has not guaranteed that men will be able to conduct their lives as free men. Those societies where men know they are free are often democracies, but sometimes they have strong chiefs and kings. ... they have, however, one common characteristic: they are all alike in making certain freedoms common to all citizens, and inalienable.”
—Ruth Benedict (1887–1948)