Is my understanding of the monoid valid?

Question

So, I am studying Haskell at the moment, and I would like to confirm or debunk my understanding of the monoid.

What I understood from reading the CIS194 course is that the monoid is basically an “API” for defining a user binary operation in a user set.

What I learned more about myself, and I came across a huge number of very confusing textbooks, trying to clarify this, so I'm not sure about that.

I have a decent mathematical background, but I'm just confused in all the metaphors, and I'm looking for a clear yes / no answer to my understanding of the 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 a single element.

I think your understanding is correct. From a programming point of view, Monoid is an interface with two “methods” that must be implemented.

The only piece that seems to be missing from your description is the “person” without whom you describe Semigroup .

Anything that has a “zero” or “empty” and a way to combine the two values ​​can be a monoid. It should be noted that it may be possible for a type / type to be made a monoid in more than one way, for example, numbers through addition with identifier 0 or multiplication with identifier 1 .

Answer 2

from tungsten:

A monoid is a set closed under an associative binary operation and having a unit element i in S such that for all a from S, Ia = aI = a.

from the Wiki:

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

so that your intuition is more or less correct.

You should keep in mind that it is not defined for a “custom set” in Haskell, but a type. The difference is small (because types of type theory are very similar to sets in set theory), but types for which you can define an instance of Monoid do not have to be types representing mathematical sets.

In other words: a type describes the set of all values ​​of this type. Monoid is an “interface” that states that any type that claims to adhere to this interface must provide an identifier value, a binary operation combining two values ​​of this type, and there are some equations that they must satisfy in order to all common Monoid operations work as intended (for example, summarizing the list of monoid values ​​in total) and do not produce illogical / inconsistent results.

In addition, note that in order for the type to be an instance of the Monoid class, the existence of an identification element in this set (type) is required.

For example, natural numbers form a monoid when added (identity = 0 ):

 0 + n = n n + 0 = n 

as well as multiplication (identity = 1 ):

 1 * n = n n * 1 = n 

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

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

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

 id . f = f f . id = f 

therefore, it is important to keep in mind that Monoid does not apply to types that are sets, but about types if they are treated as sets, so to speak.

---

as an example of an invalid 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 the mconcat list of MyInt values, you will always get MyInt 0 as the result, because the identifier value 0 and the binary operation * do not work well:

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

Answer 3

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

However, the meaning of the monoid concept lies in its relation to other types and classes. Culturally, we decided that <> is a natural way of combining / adding two things of the same type.

Consider the following example:

 {-# LANGUAGE OverloadedStrings #-} import Data.Monoid greet x = "Hello, " <> x 

The greet function is extremely polymorphic - x can be a string, a byte string, or text to name a few possibilities. Moreover, in each of these cases, it does basically what you expect from it - it adds x to the "Hello" line.

In addition, there are many algorithms that will work on what can be accumulated, and these are good candidates for generalization to a monoid. For example, consider the foldMap function of the foldMap class:

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

Not only foldMap generalize the idea of ​​folding by structure, but I can generalize how accumulation occurs by substituting the correct Monoid instance.

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

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