Haskell Monoids

A Monoid in Haskell is a Type Class that represents Types that can be combined in an associative way and have an identity element.

They are primarily used to show how to combine all values in a data structure to give a single value, usually in combination with Foldables.

Mathematical Inspiration

It is inspired by monoids from mathematics that is a triplet $(M,\cdot ,e)$ where:

• $M$ is a set.
• $\cdot$ is a binary operator $M\times M\to M$
• $e$ is the identity element of M.

which satisfy the axioms:

• Associativity: $\forall a,b,c\in M:(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• Identity: $\forall a\in M:e\cdot a=a\cdot e=e$

Haskell Declaration

A monoid has the following built-in class declaration from Data.Monoid:

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a
 
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

So for a Type a to be an instance of the class Monoid it must support a value mempty and a Function mappend that matches the declared types.

The mconcat is simply a built-in Function that combines a List of values within a monoid.

• mempty plays the role of the identity element
• mappend plays the role of the binary operator.
  • can also be used infix as <>.

They must as in mathematics satisfy associativity and identity:

mempty `mappend` x = x
x `mappend` mempty = x
x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z

Note that multiple instance declarations of the same type for the same class are not permitted in Haskell. One must instead define different types with dummy constructors to get around this.

Examples

Mathematical Monoids

We have that integers form a monoid under addition where 0 is the identity element. So $(\mathbb{R},+,0)$ is a monoid.

We also have that integers form a monoid under multiplication where 1 is the identity element. So $(\mathbb{R},\text{*},1)$ is a monoid.

mconcat on [x,y,z]

x `mappend` (y `mappend` (z `mappend` mempty))

Int Monoid under Addition

instance Monoid Int where
  -- mempty :: Int
  mempty = 0
 
  -- mappend :: Int -> Int -> Int
  mappend = (+)

List Monoid

Monoid provided in the Data.Monoid library

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

which is where the names for mempty and mappend comes from.

Maybe Monoid

instance Monoid a => Monoid (Maybe a) where
  -- mempty :: Maybe a
  mempty = Nothing
 
  -- mappend :: Maybe a -> Maybe a -> Maybe a
  Nothing `mappend` my = my
  mx `mappend` Nothing = mx
  Just x `mappend` Just y = Just (x `mappend` y)