Skip to content

Interlude: Monoids

Before discussing our second abstraction of containers—folds—we need to introduce another mathematical concept that figures quite prominently in the Foldable type class that captures folds: the monoid.

Oh dear, another greek word. What on earth is a monoid? In mathematics, a monoid is a set \(M\) with an operation \(\circ : M \times M \rightarrow M\), often called multiplication. So we can take two elements in \(M\) and multiply them to obtain another element in \(M\), their product. For \((M, \circ)\) to be a monoid, it needs to satisfy two conditions:

  • Identity: There must exist an element \(e \in M\) that is the left and right unit of multiplication: \(e \circ x = x = x \circ e\) for every \(x \in M\).

  • Associativity: For any three elements \(x, y, z \in M\), we need to have \((x \circ y) \circ z = x \circ (y \circ z)\).

Thus, \((\mathbb{Z}, +)\) and \((\mathbb{Z}, *)\) are monoids. Both addition and multiplication are associative. The unit of addition is 0. The unit of multiplication is 1. Lists together with list concatenation also form a monoid. List concatenation is associative. The unit element is the empty list because prepending or appending it to any list xs produces xs. In mathematics, this list monoid is also known as the free monoid generated by the type of the list elements.

In Haskell, monoids are captured by the Monoid type class:1

class Semigroup m => Monoid m where
    mappend :: m -> m -> m    -- The multiplication operation
    mempty  :: m              -- The unit element

As the class definition says, we actually have Monoid as a subclass of Semigroup, just as in mathematics. In mathematics, a semigroup is the same as a monoid, but it does not have to have a unit. So there only has to be a multiplication operation that is associative. A better way to say this is that a semigroup \((M, \circ)\) is a set \(M\) equipped with an associative multiplication \(\circ\), and a monoid is a semigroup \((M, \circ)\) with a multiplicative unit. This concept of a semigroup is captured by the following type class in Haskell that is a superclass of Monoid:

class Semigroup m where
    (<>) :: m -> m -> m

The default implementation of mappend then is

mappend = (<>)

because the monoid multiplication is expected to be exactly the same as the semigroup multiplication: a monoid is simply a semigroup with a unit.

Indeed, mappend is kept mainly for backward compatibility, as the Monoid type class with functions mappend and mempty was added to the Haskell standard library before factoring out the weaker concept of a semigroup into its own type class.

The addition and multiplication monoids can be expressed as follows:

Sum
newtype Sum a = Sum { getSum :: a }

instance Num a => Semigroup (Sum a) where
    Sum x <> Sum y = Sum (x + y)

instance Num a => Monoid (Sum a) where
    mempty = Sum 0
Product
newtype Product a = Product { getProduct :: a }

instance Num a => Semigroup (Product a) where
    Product x <> Product y = Prod (x * y)

instance Num a => Monoid (Product a) where
    mempty = Prod 1

The list monoid is expressed by the following instance

instance Semigroup [a] where
    (<>) = (++)    -- Multiplication is list concatenation

instance Monoid [a] where
    mempty = []    -- The unit is the empty list

All of these monoid instances are defined already in the standard library. The list monoid is available as part of the Prelude. To use Sum and Product, you need to import Data.Monoid.

GHCi
>>> import Data.Monoid
>>> getSum (Sum 3 <> Sum 5)
8
>>> getProduct (Product 3 <> Product 5)
15

We'll play with these monoids in the next section, as part of our discussion of foldable containers.

  1. The naming of the two functions in the Monoid type class stems from lists being monoids. For lists, list concatenation, or appending a list to another, is the multiplication operation. Thus, we might call monoid multiplication "monoidal append", mappend. Similarly, the empty list is the unit for list concatenation, so we may want to call the unit for any monoid the "monoidal empty list", mempty. ↩