Is my understanding of monoid valid?

Question

So, I'm learning Haskell at the moment, and I would like to confirm or debunk my understanding of monoid.

What I figured out from reading CIS194 course is that monoid is basically "API" for defining custom binary operation on custom set.

Than I went to inform my self some more and I stumbled upon massive ammount of very confusing tutorials trying to clarify the thing, so I'm not so sure anymore.

I have decent mathematical background, but I just got confused from all the metaphors and am looking for clear yes/no answer to my understanding of monoid.

Answer 1

From Wikipedia:

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I think your understanding is correct. From a programming perspective, Monoid is an interface with two "methods" that must be implemented.

The only piece that seems to be missing from your description is the "identity", without which you are describing a Semigroup.

Anything that has a "zero" or an "empty" and a way of combining two values can be a Monoid. One thing to note is that it may be possible for a set/type to be made a Monoid in more than one way, for example numbers via addition with identity 0, or multiplication with identity 1.

Answer 2

from Wolfram:

A monoid is a set that is closed under an associative binary operation and has an identity element I in S such that for all a in S, Ia=aI=a.

from Wiki:

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

so your intuition is more or less right.

You should only keep in mind that it's not defined for a "custom set" in Haskell but a type. The distinction is small (because types in type theory are very similar to sets in set theory) but the types for which you can define a Monoid instance need not be types that represent mathematical sets.

In other words: a type describes the set of all values that are of that type. Monoid is an "interface" that states that any type that claims to adhere to that interface must provide an identity value, a binary operation combining two values of that type, and there are some equations these should satisfy in order for all generic Monoid operations to work as intended (such as the generic summation of a list of monoid values) and not produce illogical/inconsistent results.

Also, note that the existence of an identity element in that set (type) is required for a type to be an instance of the Monoid class.

For example, natural numbers form a Monoid under both addition (identity = 0):

0 + n = n
n + 0 = n

as well as multiplication (identity = 1):

1 * n = n
n * 1 = n

also lists form a monoid under ++ (identity = []):

[] ++ xs = xs
xs ++ [] = xs

also, functions of type a -> a form a monoid under composition (identity = id)

id . f = f
f . id = f

so it's important to keep in mind that Monoid isn't about types that represents sets but about types when viewed as sets, so to say.

---

as an example of a malconstructed Monoid instance, consider:

import Data.Monoid

newtype MyInt = MyInt Int deriving Show

instance Monoid MyInt where
  mempty = MyInt 0
  mappend (MyInt a) (MyInt b) = MyInt (a * b)

if you now try to mconcat a list of MyInt values, you'll always get MyInt 0 as the result because the identity value 0 and binary operation * don't play well together:

λ> mconcat [MyInt 1, MyInt 2]
MyInt 0