[2008.07.10] Functions, Monoids and Monads [Part II/IV]

[2] MONOIDS

• a monoid is collection of items with a way of putting two items in the collection together, independent of what the items are
• in addition, a monoid has two rules: an associativity operation and an identity element
• define the dot operation to model function composition so f·g is a new function
• also (f·g)a means that we apply our new function to the argument a
• note that (f·g)a = g(f(a)) [1]
• now we can remove the parenthesis on the left hand side of [1] and give the new function a name such that (f·g) = h
• after this composition, we have to figure out what the type of h is, which is easy in this case: since f takes an a and returns an a, and g takes an a and returns an a, then h also takes an a and returns an a
• therefore the composition of f and g can be shown as: f·g = h: a -> a
• this composition, the act of taking two simple things of the same type and have a rule to combine them into something more complex of the same type is basically the essence of what a monoid is

Rules of Monoids

• [1] Associativity: x·(y·z) = (x·y)·z
• [2] Identity: a monoid must contain a special member such that x combined with the special member is always x (in F# this member is called unit): x + unit = x
• a monoid does not have to satisfy commutativity: x·y != y·x