## Introduction

Some very brief notes summarizing Haskell’s monoids. It’s my crib sheet, written partly to straighten matters in my own mind and partly for future reference.

Most of the information here comes from elsewhere: see a list at the end of the article. I’m also indebted to Dominic Prior for many helpful discussions. Dominic is collecting useful and interesting code^{1} on Google Docs.

## Groups

Many people are familiar with groups.^{2} Every group has:

- an associative, binary operation ⊕;
- a set of elements closed under ⊕;
- an identity element;
- an inverse element.

For example, consider the integers under addition.

We have:

- associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c);
- an identity, 0: a ⊕ 0 = 0 ⊕ a = a;
- an inverse, -a: a ⊕ (-a) = (-a) ⊕ a = 0.

## Semigroups

Now, consider instead the positive integers under addition. We still have an interesting structure, but because the set of elements does not include 0 there’s no identity element. Similarly the lack of negative numbers means there’s no inverse.

Such a structure is called a semigroup^{3}

Moving away from the integers, the set of strings of finite, non-zero length forms a semigroup under concatenation.

## Monoids

Perhaps throwing away both the inverses and the identity is too much. If we have inverses we must have the identity, but the converse isn’t true. So, let’s consider a group without inverses. This is a monoid.

Three examples come easily to mind:

Set | Operation | Identity |
---|---|---|

Natural Numbers | + | 0 |

Positive Integers | * | 1 |

Strings | ++ | "" |

Given that such basic things admit a monoidal structure, it is not surprising to find more complicated things do too. For example, Brent Yorgey’s fine diagrams^{4} package provides a monoidal instance^{5} for diagrams. In words, we can combine two diagrams to make a new diagram.

## Data.Monoid

In Haskell the monoid typeclass lives in Data.Monoid^{6} which gives us:

- the associative operator
`mappend`

or`<>`

, - the identity element
`mempty`

,

both are subject to laws:

`mempty`

`<>`

`a`

=`a`

,`a`

`<>`

`mempty`

=`a`

,- (
`a`

`<>`

`b`

)`<>`

`c`

=`a`

`<>`

(`b`

`<>`

`c`

).

Note that you really ought to use `mappend`

when implementing your own monoids, but it’s just too ugly for me.

Further, there is a `mconcat`

method which combines a list of elements. There’s a default implementation which simply folds `<>`

, but instances might be able to implement it more efficiently.

You can see that the function names are somewhat inspired by the list instance:

```
instance Monoid [a] where
mempty = []
mappend = ++
```

So we can concatenate lists more abstractly:

```
> "the " <> "quick"
"the quick"
> mempty <> "quick"
"quick"
> mconcat [ "the ", "quick ", "brown " ]
"the quick brown "
```

Now let’s turn to the integers. Recall that there are two different monoids: one under multiplication and the other under addition. Haskell handles this with two different classes: `Product`

and `Sum`

respectively.

```
> Product 2 <> Product 3
Product {getProduct = 6}
> Product 2 <> mempty
Product {getProduct = 2}
> Sum 2 <> Sum 3
Sum {getSum = 5}
> Sum 2 <> Sum 0
Sum {getSum = 2}
> Sum 2 <> mempty
Sum {getSum = 2}
> mconcat $ map Sum [1..10]
Sum {getSum = 55}
> mconcat $ map Product [1..10]
Product {getProduct = 3628800}
```

The instance implementation looks like this:

```
newtype Product a = Product { getProduct :: a }
deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
instance Num a => Monoid (Product a) where
mempty = Product 1
Product x <> Product y = Product $ x * y
```

## The Maybe monoid

We can often think of the Maybe type as being a special case of lists with at most one element, and so unsurprisingly there’s a monoid instance for Maybe too:

```
> Just "a" <> Just "b"
Just "ab"
> Nothing <> Just "b"
Just "b"
> mempty <> Just "b"
Just "b"
> mconcat $ map ((\x -> Just [x]) ['a' .. 'f']
Just "abcdef"
```

An implementation is straightforward:

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

Assuming that `mempty`

= `Nothing`

the last three equations follow from the monoid laws, but we have more freedom when evaluating

` Just a <> Just b`

Ignoring `Just $ a <> b`

there are only two choices:

`Just a`

`Just b`

and it turns out that both choices have been instantiated as `First`

and `Last`

. We’ll consider `First`

in more detail:

```
newtype First a = First { getFirst :: Maybe a }
deriving (Eq, Ord, Read, Show, Generic, Generic1,
Functor, Applicative, Monad)
instance Monoid (First a) where
mempty = First Nothing
First (Just a) <> First (Just b) = First $ Just a
First (Just a) <> First (Nothing) = First $ Just a
First (Nothing) <> First (Just b) = First $ Just b
First (Nothing) <> First (Nothing) = First Nothing
```

So we have a way of picking out the first or last interesting entry. For example, let’s set up a little database with just a couple of interesting characters in it: a and b:

```
> let interesting = [ 'a', 'b' ]
> let q c = if c `elem` interesting then Just c else Nothing
> q 'a'
Just 'a'
> q 'c'
Nothing
```

Now let’s look at the monoids:

```
> mconcat $ map (First . q) "cabinet"
First {getFirst = Just 'a'}
> mconcat $ map (Last . q) "cabinet"
Last {getLast = Just 'b'}
> mconcat $ map (Last . q) "desk"
Last {getLast = Nothing}
```

Note that because we are *selecting* one of the existing values and *not creating* one, we don’t need the underlying data type to be a monoid inself. This isn’t the case with the plain Maybe monoid.

## Maximum, AND, OR

Given a set of numbers we could form another monoid over maximum. There’s no standard instance, but it’s easy to write one. In fact, it’s easy to write two!

The key decision is `mempty`

. We could just reuse Maybe:

```
newtype MaxM a = MaxM { getMaxM :: Maybe a }
deriving (Eq, Ord, Read, Show)
instance Monoid (MaxM a) where
mempty = MaxM Nothing
a <> MaxM Nothing = a
MaxM Nothing <> b = b
MaxM (Just a) <> MaxM (Just b) = MaxM . Just $ max a b
```

Alternatively we could make `mempty`

the lower bound for the type in question (if such a thing exists):

```
newtype MaxB a = MaxB { getMaxB :: a }
deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
instance Num a => Monoid (MaxB a) where
mempty = minBound
mappend = max
```

Note that because `minBound`

depends on the type, we’ll often have to explicit supply one:

```
> MaxB 1 <> MaxB 2 :: MaxB Int
MaxB {getMaxB = 2}
```

We can play games with different types:

```
> import Data.Int
> import Data.Word
> mempty :: MaxB Int16
MaxB {getMaxB = -32768}
> mempty :: MaxB Word16
MaxB {getMaxB = 0}
> mempty :: MaxB Int
MaxB {getMaxB = -9223372036854775808}
```

But not `Integer`

: being unbounded it doesn’t have a bound!

```
> mempty :: MaxB Integer
<interactive>:...:
No instance for (Bounded Integer) arising from a use of ‘mempty’
In the expression: mempty :: MaxB Integer
In an equation for ‘it’: it = mempty :: MaxB Integer
```

At the other end of the size scale, consider 1-bit integers. With the usual equivalences, 0 ≡ False and 1 ≡ True, we find `max`

≡ `||`

and `min`

≡ `&&`

. These instances are standard ones: `Any`

and `All`

:

```
> Any True <> Any True
Any {getAny = True}
> Any True <> Any False
Any {getAny = True}
> All True <> All True
All {getAll = True}
> All True <> All False
All {getAll = False}
```

## Ordering

Haskell defines a comparison function for the `Ord`

typeclass. `a `compare` b`

will return:

`EQ`

if`a`

=`b`

;`GT`

if`a`

>`b`

;`LT`

if`a`

<`b`

.

If we define a monoid instance akin to First, where EQ plays the role of Nothing, then we’ll get first-is-most-significant comparisons.

```
instance Monoid Ordering where
mempty = EQ
EQ <> b = b
a <> _ = a
> mconcat $ zipWith compare [1,8,9] [3,4,5]
LT
```

However, the real trick, which I first saw on reddit^{7} is to append two comparison functions:

```
> :t comparing length
comparing length :: [a] -> [a] -> Ordering
> :t compare
compare :: Ord a => a -> a -> Ordering
> :t comparing length <> compare
comparing length <> compare :: Ord a => [a] -> [a] -> Ordering
> sortBy (comparing length <> compare) $ words "the quick brown fox"
["fox","the","brown","quick"]
```

## The Writer Monad

Finally, a common use for monoids is the Writer monad: the things we log must be monoidal. In modern parlance we should refer to the MonadWriter class.^{8}

Following Chris Taylor on StackOverflow,^{9} let’s define as toy action, parameterized by the logging method:

```
import Control.Monad.Writer
> let toyAction l = do { a <- l 3; b <- l 5; return (a*b) }
```

Let’s start with a fairly traditional log:

```
> let logS x = writer (x, "Got " ++ show x ++ "\n")
> runWriter $ toyAction logS
(15,"Got 3\nGot 5\n")
```

or a list of numbers encountered:

```
> let logN x = writer (x, [x])
> runWriter $ toyAction logN
(15,[3,5])
```

or just a count of them:

```
> let logA x = writer (x, Sum 1)
> runWriter $ toyAction logA
(15,Sum {getSum = 2})
```

## Endo

Endomorphisms^{10} are maps from a thing to itself, which in Haskell terms means functions of type `(a -> a)`

. You can make a monoid from these under function composition:

```
> (+2) . (+3) $ 10
15
> (appEndo $ Endo (+2) <> Endo (+3)) 10
15
```

## Foldable

The Foldable typeclass models reducing a set of things to a single value. The minimal implementation is either `foldr`

or `foldMap`

. The latter is perhaps most interesting here:

`foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m`

If we specialize to a list to get an intuitive picture:

```
foldMap :: (Monoid m) => (a -> m) -> [a] -> m
foldMap f = mconcat . fmap f
```

In other words to apply `foldMap`

, first map things into a Monoid, and then collapse the structure with `mconcat`

. We used exactly this construction above, and so those examples can be expressed more succinctly with `foldMap`

. For example:

```
> foldMap Sum [1..10]
Sum {getSum = 55}
> foldMap Product [1..10]
Product {getProduct = 3628800}
```

The trick to expressing `foldr`

in terms of `foldr`

in terms of `foldMap`

is to note that the step function in `foldr`

has type:

`(a -> b -> b) = (a -> (b -> b))`

and that `(b -> b)`

forms a monoid under composition (see Endo above). So to `foldr`

on a list of `[a]`

:

- map all the
`a`

into transformations functions with type`b -> b`

; - compose those functions into one overall transform;
- apply that to the starting
`b`

.

You can read a fuller explanation of this in the Haskell wikibook^{11}.

## Other discussions

Most of the material here has been stolen from other pages. If you want to consult these primary sources I recommend:

- The typeclassopedia;
^{12} - a 2009 article by Dan Piponi;
^{13} - and Heinrich Apfelmus’ article on annotated trees.
^{14}

## References

- 1. https://docs.google.com/document/d/1DvbcQTibeUEOVmoLO14vvRa27kf6y29sObUmQpyFn9g/pub
- 2. http://en.wikipedia.org/wiki/Group_(mathematics)
- 3. https://en.wikipedia.org/wiki/Semigroup
- 4. http://projects.haskell.org/diagrams/
- 5. http://projects.haskell.org/diagrams/doc/manual.html#semigroups-and-monoids
- 6. https://downloads.haskell.org/~ghc/latest/docs/html/libraries/base/Data-Monoid.html
- 7. http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx
- 8. http://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-Writer-Lazy.html#g:1
- 9. http://stackoverflow.com/questions/11684321/how-to-play-with-control-monad-writer-in-haskell
- 10. https://en.wikipedia.org/wiki/Endomorphism
- 11. https://en.wikibooks.org/wiki/Haskell/Foldable
- 12. https://wiki.haskell.org/Typeclassopedia#Monoid
- 13. http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html
- 14. http://apfelmus.nfshost.com/articles/monoid-fingertree.html