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

At a basic level you're right - it's just an API for a binary operator we denote by <>.

However, the value of the monoid concept is in its relationship to other types and classes. Culturally we've decided that <> is the natural way of joining/appending two things of the same type together.

Consider this example:

{-# LANGUAGE OverloadedStrings #-}

import Data.Monoid

greet x = "Hello, " <> x

The function greet is extremely polymorphic - x can be a String, ByteString or Text just to name a few possibilities. Moreover, in each of these cases it does basically what you expect it to - it appends x to the string `"Hello, ".

Additionally, there are lots of algorithms which will work on anything that can be accumulated, and those are good candidates for generalization to a Monoid. For example consider the foldMap function from the Foldable class:

foldMap ::  Monoid m => (a -> m) -> t a -> m

Not only does foldMap generalize the idea of folding over a structure, but I can generalize how the accumulation is performed by substituting the right Monoid instance.

If I have a foldable structure t containing Ints, I can use foldMap with the Sum monoid to get the sum of the Ints, or with Product to get the product, etc.

Finally, using <> affords convenience. For instance, there is an abundance of different Set implementations, but for all of them s <> t is always the union of two sets s and t (of the same type). This enables me to write code which is agnostic of the underlying implementation of the set thereby simplifying my code. The same can be said for a lot of other data structures, e.g. sequences, trees, maps, priority queues, etc.

Answer 3

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