Monoids

A monoid is a single object category. In fact the name monoid comes from Greek mono, which means single.

Monoid is an embarrassingly simple but amazingly powerful concept. It’s the concept behind basic arithmetics: Both addition and multiplication form a monoid. Monoids are ubiquitous in programming.

Every monoid can be described as a single object category with a set of morphisms that follow appropriate rules of composition.

• Traditionally, a monoid is defined as a set with a binary operation.

Intuitively, a monoid is a structure that allows for combining elements in a well-defined way, and has an element that serves as a “starting point” for this process.

Formally, a monoid is a tuple (M, ∗, e), where M is a set, ∗ is a binary operation on M, and e is an element of M, such that:

1. ∀a,b ∈ M, a ∗ b ∈ M
2. ∀a,b,c ∈ M, (a ∗ b) ∗ c = a ∗ (b ∗ c)
3. ∀a ∈ M, e ∗ a = a ∗ e = a

In Haskell we can define a type class for monoids — a type for which there is a neutral element called mempty and a binary operation called mappend:

class Monoid m where
		mempty :: m
		mappend :: m -> m -> m

As an example, let’s declare String to be a monoid by providing the implementation of mempty and mappend (this is, in fact, done for you in the standard Prelude):

instance Monoid String where
		mempty = ""
		mappend = (++)

The closest one can get to declaring a monoid in C++ would be to use the (proposed) syntax for concepts.

template<class T>
		T mempty = delete;
 
template<class T>
		T mappend(T, T) = delete;
 
template<class M>
		concept bool Monoid = requires (M m) {
		{ mempty<M> } -> M;
		{ mappend(m, m); } -> M;
};

The first definition uses a value template (also proposed). A polymorphic value is a family of values — a different value for every type.

The keyword delete means that there is no default value defined: It will have to be specified on a case-by-case basis. Similarly, there is no default for mappend. The concept Monoid is a predicate (hence the bool type) that tests whether there exist appropriate definitions of mempty and mappend for a given type M.

An instantiation of the Monoid concept can be accomplished by providing appropriate specializations and overloads:

template<>
std::string memptystd::string = {""};
std::string mappend(std::string s1, std::string s2) {
	return s1 + s2;
}

---

https://www.youtube.com/watch?v=INnattuluiM

https://www.youtube.com/watch?v=BovTQeDK7XI

---

🌱 Back to Garden