Tuesday, July 22, 2008

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


  • 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

No comments: