# Difference between revisions of "Monoid"

Benmachine (talk | contribs) m (→So what?: style) |
Benmachine (talk | contribs) (→See also: cut some unnecessary stuff) |
||

Line 70: | Line 70: | ||

== See also == | == See also == | ||

− | + | * [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses] | |

− | * | + | * [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees] |

− | * | ||

* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up] | * [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up] | ||

Generalizations of monoids feature in [[Category theory]], for example: | Generalizations of monoids feature in [[Category theory]], for example: | ||

* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF) | * [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF) |

## Revision as of 15:01, 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 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

- Haskell Monoids and their Uses
- 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: