# Difference between revisions of "Monoid"

Rimmington (talk | contribs) m (fixed "Arrows, like Monads, are Monoids" link) |
Benmachine (talk | contribs) (rewrite) |
||

Line 1: | Line 1: | ||

− | + | 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 == | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | <haskell> | |

− | + | 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 also useful | ||

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

+ | </haskell> | ||

+ | |||

+ | together with the following laws: | ||

+ | |||

+ | <haskell> | ||

+ | -- Identity laws | ||

+ | x <> mempty = x | ||

+ | mempty <> x = x | ||

+ | |||

+ | -- Associativity | ||

+ | (x <> y) <> z = x <> (y <> z) | ||

+ | </haskell> | ||

+ | |||

+ | == Examples == | ||

+ | |||

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

+ | |||

+ | <haskell> | ||

+ | instance Monoid [a] where | ||

+ | mempty = [] | ||

+ | mappend x y = x ++ y | ||

+ | mconcat = concat | ||

+ | </haskell> | ||

+ | |||

+ | Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>. | ||

+ | |||

+ | 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 [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them: | ||

+ | |||

+ | <haskell> | ||

+ | 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) | ||

+ | </haskell> | ||

+ | |||

+ | Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>. | ||

+ | |||

+ | == 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 [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> 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 <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically": | ||

+ | |||

+ | <haskell> | ||

+ | sortStrings = sortBy (comparing length <> compare) | ||

+ | </haskell> | ||

+ | |||

+ | 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.: | The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.: |

## Revision as of 14:22, 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*.

## Contents

## 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 also useful
x <> y = mappend x y
```

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: