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 American adolescent, then, is faced, as are the adolescents of all countries who have entered or are entering the machine age, with the question: freedom from what and at what price? The American feels so rich in his opportunities for free expression that he often no longer knows what it is he is free from. Neither does he know where he is not free; he does not recognize his native autocrats when he sees them.”
—Erik H. Erikson (1904–1994)