# Difference between revisions of "Monoid"

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

Line 1: | Line 1: | ||

− | {{Stub}} |
||

+ | 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''. |
||

− | A monoid is an algebraic structure with an associative binary operation that has an identity element. Examples include: |
||

+ | == Declaration == |
||

− | * lists under concatenation |
||

− | * numbers under addition or multiplication |
||

− | * Booleans under conjunction or disjunction |
||

− | * sets under union or intersection |
||

− | * functions from a type to itself, under composition |
||

− | Note that in most of these cases the operation is also commutative, but it need not be; concatenation and function composition are not commutative. |
||

+ | <haskell> |
||

− | |||

+ | class Monoid m where |
||

− | A Monoid class is defined in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html Data.Monoid], and used in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable] and in the Writer monad. |
||

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