# Monoid

Contents

A monoid is an algebraic structure comprising a product of three things

• a set;
• a closed binary operation; and
• an element of the set that is neutral with respect to that binary operation.

The binary operation must be associative.

In other words, a monoid is a semigroup with one additional requirement: the identity value.

Many sets form monoids under more than one operation. Integers, for example, form monoids under both sum and product operations, with 0 being the neutral element for addition and 1 being the identity for multiplication.

## The `Monoid` class

In Haskell, monoids are represented by the `Monoid` class. `Monoid` is superclassed by `Semigroup`Since `base-4.11.0.0`., which means there is a `Semigroup` constraint on the `Monoid` class in the class definition. This means that in order to have a `Monoid` instance, a type must also have a `Semigroup` instance.

``````class Semigroup a => Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
{-# MINIMAL mempty #-}``````

The `mappend` function was formerly part of the minimal complete definition of `Monoid`, and `<>` was its infix version; however, since all `Monoid`s must also be `Semigroup`s, the presence of `mappend` in `Monoid` is superfluous. The binary operation for a monoid is its implementation of `<>` from the `Semigroup` class. You may still use `mappend` if you prefer prefix functions in some cases, and for historical reasons, you’ll still see it in a lot of Haskell code.

Now the only thing that must be implemented for an `instance` of `Monoid` is `mempty`. As you can see, it’s not a function, In some senses, it is a function. Since a typeclass can also be conceived as a record of functions that is passed around implicitly, the `Monoid a =>` constraint on `mempty` can be read as a function: it needs to be applied to a type in order to return the value. but nevertheless it’s very important: it defines the identity or neutral element with regard to the set and the particular operation. Thus, for numbers that form a monoid under addition, denoted with the `Sum` newtype, `mempty` would be `Sum 0`; for the `Product` newtype, it would be `Product 1`.

``````λ> Sum 2 <> Sum 0
Sum {getSum = 2}

λ> Sum 2 <> mempty
Sum {getSum = 2}

λ> Product 1 <> Product 5
Product {getProduct = 5}

λ> mempty <> Product 5
Product {getProduct = 5}

λ> Product 0 <> Product 5
Product {getProduct = 0}``````

`mempty` is return-type polymorphic and is useful in writing polymorphic functions where an identity value of some kind will be needed but the type cannot yet be known. For example, we see this commonly used in the `pure` implementation for `Applicative` instances on certain species of types, such as tuples:

``````instance Monoid a => Applicative ((,) a) where

pure x =
(mempty, x)

(x, func) <*> (y, z) =
(x <> y, func z)

liftA2 func (x, z) (y, z') =
(x <> y, func z z')``````

It’s worth noting that `Monoid` should obey right and left identity laws. It shouldn’t too be surprising given what we expect of an identity value; if it’s neutral with respect to the operation, it should be neutral regardless of whether it’s the first argument or the second.

``````mempty <> x = x
-- and --
x <> mempty = x``````

For example, it would be a truly unwanted surprise if multiplying by 1 gave you a different result depending on which position the 1 was in.

``````λ> mempty <> Product 5
Product {getProduct = 5}

λ> Product 5 <> mempty
Product {getProduct = 5}``````

This is particularly trivial, though, since multiplication is known to be commutative. Not all monoids are commutative! For example, list concatenation is associative but not commutative: changing the order of arguments in list concatenation gives different results.

``````λ> "Julie" <> "Moronuki"
"JulieMoronuki"

λ> "Moronuki" <> "Julie"
"MoronukiJulie"``````

However, it is still the case that its `mempty` behaves itself as both the right and left identity.

``````λ> "Julie" <> mempty
"Julie"

λ> mempty <> "Julie"
"Julie"``````

## mconcat

In terms of Haskell history, `Monoid` precedes `Semigroup`, so `mconcat` is in the `Prelude` while `sconcat` is not. They are essentially the same function, however, but with `mconcat` requiring a standard list input instead of a `NonEmpty`.

``mconcat :: Monoid a => [a] -> a``

The single input of `mconcat` is a list; the type of the values in the list must be a monoid. The monoidal operation (the `mappend`, also known as `(<>)` from `Semigroup`) is used to reduce them to a single value.

If the argument is a list of list monoids, you get the original `concat`.The `@` in this example is a type application, and the underscore is a type wildcard.

``````λ> :type mconcat @[_]
mconcat @[_] :: [[w]] -> [w]

λ> :type concat @[]
concat @[] :: [[a]] -> [a]

λ> mconcat ["julie", "moronuki"]
"juliemoronuki"

λ> mconcat [[1, 2], [4, 5]]
[1,2,4,5]

λ> concat [[1, 2], [4, 5]]
[1,2,4,5]``````

If your monoid is one of the arithmetic monoids, then `mconcat` is similar to the `sum` and `product` functions – both of which are in `Prelude` – although they accept any `Foldable` containers as inputs, not only lists.

``````λ> :type sum
sum :: (Foldable t, Num a) => t a -> a

λ> :type product
product :: (Foldable t, Num a) => t a -> a

λ> sum [3, 4, 5]
12

λ> product [3, 4, 5]
60

λ> mconcat [Sum 3, Sum 4, Sum 5]
Sum {getSum = 12}

λ> mconcat [Product 3, Product 4, Product 5]
Product {getProduct = 60}``````

Some monoidsPlease note that the `First` and `Last` types in `Data.Monoid` are different from those in `Data.Semigroup`. See the section below on the monoid newtypes for more information. “choose” an element to return (instead of “combining” them), such as the Boolean monoids `Any` and `All` or the `Maybe` monoids `First` and `Last`, and so will always return one of the elements that is actually in the list.

``````λ> mconcat [Any True, Any False, Any False]
Any {getAny = True}

λ> mconcat [All True, All False, All False]
All {getAll = False}

λ> mconcat [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> mconcat [Last (Just 3), Last Nothing, Last (Just 5)]
Last {getLast = Just 5}``````

Reducing a collection of values to a single value, often called reduce in other languages, is typically referred to as folding in Haskell. And, indeed, `mconcat` is further generalized by a function called `fold` from the `Data.Foldable` module.

``````λ> :type fold
fold :: (Foldable t, Monoid m) => t m -> m

λ> mconcat [Just "julie", Nothing, Just "moronuki"]
Just "juliemoronuki"

λ> fold [Just "julie", Nothing, Just "moronuki"]
Just "juliemoronuki"

λ> mconcat [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> fold [First (Just 3), First Nothing, First (Just 5)]
First {getFirst = Just 3}

λ> mconcat [Product 3, Product 4, Product 5]
Product {getProduct = 60}

λ> fold [Product 3, Product 4, Product 5]
Product {getProduct = 60}``````

There is a deep connection between monoids and folding functions. We’ve written about it from one perspective in the past, and we will no doubt write about it again.

## Monoids and their identities

Since `Semigroup` now superclasses `Monoid`, all of the `Monoid` newtypes are also `Semigroup`s, so in some sense, the only thing to know about their `Monoid` instances is what the `mempty` is. The newtypes will be covered in more detail below, but essentially `mempty` values come in two flavors: 1 and 0.