Free Monoid - Free Monoids and Computing

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(x₁…x_n) = f(x₁) • … • f(x_n)
• 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.