# Monoid

### From HaskellWiki

m (Links fixed) |
Benmachine (Talk | contribs) (→On the Writer monad: trim unhelpful remark) |

(9 intermediate revisions by 2 users not shown) |

## Latest revision as of 16:52, 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 |

## [edit] 1 The basics

### [edit] 1.1 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)

### [edit] 1.2 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

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)

### [edit] 1.3 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,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.

## [edit] 2 In more depth

### [edit] 2.1 On mconcat

mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:

mempty = mconcat [] mappend x y = mconcat [x, y]

What of the laws? Well, we can have the following:

mconcat [x] = x mconcat (map mconcat xss) = mconcat (concat xss)

The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.

#### [edit] 2.1.1 Categorical diversion

Note that the above two laws can also be phrased as follows:

mconcat . return = id mconcat . map mconcat = mconcat . join

### [edit] 2.2 On the Writer monad

The Writer monad is a way to put a monad structure on tuples. You write bind like this:

(w,x) >>= f = case f x of (v, y) -> (w <> v, y)

Notice that it's the monoid instance of the first component that allows you to incorporate both `w` and `v` into the final result, which seems like an important thing to do.

### [edit] 2.3 On the Const applicative

Even more straightforwardly,## [edit] 3 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: