A personal blog about computer science topics.

A Semigroup with Identity
Posted on Aug 27 2023 ~ 5 min read
#category theory  #abstract algebra 

Functor Functor Applicative Applicative Functor->Applicative Traversable Traversable Functor->Traversable Applicative->Traversable Alternative Alternative Applicative->Alternative Monad Monad Applicative->Monad Apply Apply Apply->Applicative Semigroup Semigroup Semigroup->Apply Monoid Monoid Semigroup->Monoid MonadPlus MonadPlus Monad->MonadPlus MonadFix MonadFix Monad->MonadFix ArrowApply ArrowApply Monad->ArrowApply Monoid->Applicative Monoid->Alternative Monoid->Monad Monoid->MonadPlus Category Category Monoid->Category ArrowPlus ArrowPlus Monoid->ArrowPlus Foldable Foldable Monoid->Foldable Arrow Arrow Category->Arrow Foldable->Traversable Arrow->ArrowApply ArrowChoice ArrowChoice Arrow->ArrowChoice ArrowZero ArrowZero Arrow->ArrowZero ArrowZero->ArrowPlus

In category theory, a Monoid is a triple ( M M , η \eta , μ \mu ) in a monoidal category ( C \mathcal{C} , \otimes , 1 M 1_{M} ) together with two morphisms:

  • η : 1 M M \eta: 1_{M} \rightarrow M is a natural transformation (the unit)
  • μ : M M M \mu: M \otimes M \rightarrow M is another natural transformation (the multiplication)

These must satisfy the following coherence conditions:

  • μ ( μ ( a , b ) , c ) = μ ( a , μ ( b , c ) )      a , b , c M \mu(\mu(a, b), c) = \mu(a, \mu(b, c))\ \ \forall\ a, b, c \in M (associativity)
  • μ ( η ( 1 M ) , a ) = a = μ ( a , η ( 1 M ) )      a M \mu(\eta(1_{M}), a) = a = \mu(a, \eta(1_{M}))\ \ \forall\ a \in M (left and right identiy)

We can rephrase these conditions using the subsequent commutative diagrams:

\begin{xy} \xymatrix{ M\ \otimes\ M\ \otimes\ M \ar[d]_{\mu M} \ar[r]^{M\mu} & M\ \otimes\ M \ar[d]^{\mu} \\ M\ \otimes\ M \ar[r]_{\mu} & M } \end{xy}
\begin{xy} \xymatrix{ M \ar[d]_{\eta M} \ar[r]^{M\eta} \ar@{=}[dr] & M\ \otimes\ M \ar[d]^{\mu} \\ M\ \otimes\ M \ar[r]_{\mu} & M } \end{xy}

Monoids are a powerful abstraction that can be used to solve a wide variety of problems. Monoids are becoming increasingly important in computer science because they provide a versatile framework for combining elements, especially in the context of parallel and distributed computing. For example, if you need to combine values in a way that’s associative and has an identity, you can model your problem as a monoid.

Consider using monoids for aggregations on large data sets. Because of the associative property, the operation can occur in any order and still yield the same result, enabling parallel processing. The identity element provides a starting value for this computation. The classic examples of this are sum and multiplication on numbers, but also concatenation on strings or lists and more. Monoids are also used in the design of compilers and interpreters. For example, the abstract syntax tree of a program can be represented as a monoid.


The Monoid, by definition, requires us to implement two functions: the unit, which is called mempty in Haskell, where we have to provide a neutral element, and the multiplication <> (mappend).

Haskell Definition of Monoid (Interface)

class Monoid a where
  -- η : 1 -> M (unit)
    mempty  :: a

  -- μ : M x M -> M (multiplication)
    mappend :: a -> a -> a

These have to obey the Monoid laws (<> infix notation for mappend) in pseudo notation:

(<> y) <> z = x <> (<> z) -- associativity
mempty <> x <> mempty = x     -- left and right identity

An Instance of Monoid, the List Monoid

instance Monoid [a] where
    mempty  = []
    mappend = (++)

Another Instance, the Maybe Monoid

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Just a  <> Just b  = Just (<> b)
    Just a  <> Nothing = Just a
    Nothing <> Just b  = Just b
    Nothing <> Nothing = Nothing

All of the above is already implemented in the standard Haskell library, so you can also simply open an interactive Haskell interpreter (ghci) and test the following examples.

ghci> mappend [1,2,3] [4,5,6]

ghci> [1,2,3] <> [4,5,6]

ghci> Just "A" <> Just "B"
Just "AB"

ghci> Nothing <> Just "A" <> Nothing
Just "A"

ghci> Nothing <> Nothing

Some more examples are:

  • The naturals numbers ( N 0 , + , 0 ) \left({\mathbb {N}}_{0},+,0\right) under addition. This forms a monoid because addition is associative, and 0 serves as the identity, as any number added by 0 remains the same.

  • The natural numbers ( N 0 , × , 0 ) \left({\mathbb {N}}_{0},\times,0\right) under multiplication. This forms a monoid because multiplication is associative, and 1 serves as the identity, as any number multiplied by 1 remains the same.

  • Strings ( String , + + , "" ) (\texttt{String},++,\texttt{""}) under concatenation. This forms a monoid because string concatenation is associative, and the empty string "" \texttt{""} serves as the identity, as any string concatenated with "" \texttt{""} remains the same.


  1. 0.The diagram displayed at the top of this post is a modified version of Brent Yorgey's Typeclassopedia diagram
  2. 1.Monoids in ncatlab
  3. 2.Monoids in Haskell