# Difference between revisions of "Monoid"

Benmachine (talk | contribs) (rewrite) |
Benmachine (talk | contribs) (→Declaration: fixity of <>) |
||

Line 11: | Line 11: | ||

mconcat = foldr mappend mempty |
mconcat = foldr mappend mempty |
||

− | -- this infix synonym for mappend is |
+ | -- this infix synonym for mappend is found in Data.Monoid |

x <> y = mappend x y |
x <> y = mappend x y |
||

+ | infixr 6 <> |
||

</haskell> |
</haskell> |
||

## Revision as of 14:23, 1 November 2015

In Haskell, the Monoid typeclass (not to be confused with Monad) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the *identity* element). It is closely related to the Foldable class, and indeed you can think of a Monoid instance declaration for a type *m* as precisely what you need in order to fold up a list of values of *m*.

## Declaration

```
class Monoid m where
mempty :: m
mappend :: m -> m -> m
mconcat :: [m] -> m
-- defining mconcat is optional, since it has the following default:
mconcat = foldr mappend mempty
-- this infix synonym for mappend is found in Data.Monoid
x <> y = mappend x y
infixr 6 <>
```

together with the following laws:

```
-- Identity laws
x <> mempty = x
mempty <> x = x
-- Associativity
(x <> y) <> z = x <> (y <> z)
```

## Examples

The prototypical and perhaps most important example is lists, which form a monoid under concatenation:

```
instance Monoid [a] where
mempty = []
mappend x y = x ++ y
mconcat = concat
```

Indeed, appending the empty list to either end of an existing list does nothing, and `(x ++ y) ++ z`

and `x ++ (y ++ z)`

are both the same list, namely all the elements of `x`

, then all the elements of `y`

, them all the elements of `z`

.

Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the newtypes `Sum n` and `Product n` to distinguish between them:

```
newtype Sum n = Sum n
instance Num n => Monoid (Sum n) where
mempty = Sum 0
mappend (Sum x) (Sum y) = Sum (x + y)
newtype Product n = Product n
instance Num n => Monoid (Product n) where
mempty = Sum 1
mappend (Sum x) (Sum y) = Sum (x * y)
```

Now `mconcat`

on a list of `Sum Integer`

(say) values works like `sum`

, while on a list of `Product Double`

values it works like `product`

.

## So what?

There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned Foldable, or the Writer monad, or some Applicatives). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, `Ordering`

, the standard type which Haskell uses for the result of `compare`

functions, has a "lexicographic" combination operation, where `mappend`

essentially takes the first non-equality result. Secondly, if `b`

is a Monoid, then functions of type `a -> b`

can be combined by just calling them both and combining the results. Now, of course, since `a -> a -> b`

is just a function returning a function, it can also be combined in the same way. And so you can combine comparison functions, of type `a -> a -> Ordering`

, and write the following sorts of thing, which means "sort strings by length and then alphabetically":

```
sortStrings = sortBy (comparing length <> compare)
```

Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.

## See also

The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:

- An introduction: Haskell Monoids and their Uses
- The blog article Monoids and Finger Trees
- Monad.Reader issue 11, "How to Refold a Map." (PDF), and a follow up

Generalizations of monoids feature in Category theory, for example: