Difference between revisions of "Monoid"

From HaskellWiki
Jump to: navigation, search
m (fixed "Arrows, like Monads, are Monoids" link)
(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.

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

Generalizations of monoids feature in Category theory, for example: