Menu
Looks like I have a pretty clear understanding what a Monoid is in Haskell, but last time I heard about something called a free monoid.
What is a free monoid and how does it relate to a monoid?
Can you provide an example in Haskell?
314
A monoid is a set that is closed under an associative binary operation and has an identity element such that for all , . Note that unlike a group, its elements need not have inverses. It can also be thought of as a semigroup with an identity element.
A term used as an abbreviation for the phrase "semi-group with identity" . Thus, a monoid is a set M with an associative binary operation, usually called multiplication, in which there is an element e such that ex=x=xe for any x∈M. The element e is called the identity (or unit) and is usually denoted by 1.
Examples. An abelian group is a commutative monoid that is also a group. The natural numbers (together with 0) form a commutative monoid under addition. Every bounded semilattice is an idempotent commutative monoid, and every idempotent commutative monoid yields a semilattice, (see that entry).
Examples of monoids. (1) N = {0,1,2,...} is a monoid with respect to addition. Simi- larly, N+ = N − {0} and N are both monoids with respect to multiplication. (2) For any set S, EndS, the set of all maps from S to itself, called endomorphisms, is a monoid with respect to composition.
As you already know, a monoid is a set with an element e and an operation <> satisfying
e <> x = x <> e = x (identity)
(x<>y)<>z = x<>(y<>z) (associativity)
Now, a free monoid, intuitively, is a monoid which satisfies only those equations above, and, obviously, all their consequences.
For instance, the Haskell list monoid ([a], [], (++)) is free.
By contrast, the Haskell sum monoid (Sum Int, Sum 0, \(Sum x) (Sum y) -> Sum (x+y)) is not free, since it also satisfies additional equations. For instance, it's commutative
x<>y = y<>x
and this does not follow from the first two equations.
Note that it can be proved, in maths, that all the free monoids are isomorphic to the list monoid [a]. So, "free monoid" in programming is only a fancy term for any data structure which 1) can be converted to a list, and back, with no loss of information, and 2) vice versa, a list can be converted to it, and back, with no loss of information.
In Haskell, you can mentally substitute "free monoid" with "list-like type".
200
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
