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:
“It is among the ranks of school-age children, those six- to twelve-year-olds who once avidly filled their free moments with childhood play, that the greatest change is evident. In the place of traditional, sometimes ancient childhood games that were still popular a generation ago, in the place of fantasy and make- believe play . . . todays children have substituted television viewing and, most recently, video games.”
—Marie Winn (20th century)