Difference between revisions of "Monoid"
Benmachine (talk  contribs) (rewrite) 
m (→See also) 

(11 intermediate revisions by 3 users not shown)  
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''. 
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''. 

−  == 
+  == The basics == 
+  
+  === Declaration === 

<haskell> 
<haskell> 

−  class 
+  class Semigroup m where 
+  (<>) :: m > m > m 

+  
+   defining sconcat is unnecessary, it has a default implementation 

+  sconcat :: NonEmpty m > m 

+  sconcat = ... 

+  
+   defining stimes is unnecessary, it has a default implementation 

+  stimes :: Integral a => a > m > m 

+  stimes = ... 

+  
+  infixr 6 <> 

+  
+  class Semigroup m => Monoid m where 

mempty :: m 
mempty :: m 

+  
+   defining mappend is unnecessary, it copies from Semigroup 

mappend :: m > m > m 
mappend :: m > m > m 

−  +  mappend = (<>) 

+  
 defining mconcat is optional, since it has the following default: 
 defining mconcat is optional, since it has the following default: 

⚫  
mconcat = foldr mappend mempty 
mconcat = foldr mappend mempty 

−  
−   this infix synonym for mappend is also useful 

−  x <> y = mappend x y 

</haskell> 
</haskell> 

Line 26:  Line 42:  
</haskell> 
</haskell> 

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

<haskell> 
<haskell> 

+  instance Semigroup [a] where 

+  (<>) = (++) 

+  
instance Monoid [a] where 
instance Monoid [a] where 

mempty = [] 
mempty = [] 

⚫  
⚫  
</haskell> 
</haskell> 

Line 43:  Line 60:  
<haskell> 
<haskell> 

newtype Sum n = Sum n 
newtype Sum n = Sum n 

+  
+  instance Num n => Semigroup (Sum n) where 

⚫  
instance Num n => Monoid (Sum n) where 
instance Num n => Monoid (Sum n) where 

mempty = Sum 0 
mempty = Sum 0 

⚫  
newtype Product n = Product n 
newtype Product n = Product n 

+  
+  instance Num n => Semigroup (Product n) where 

+  Product x <> Product y = Product (x * y) 

instance Num n => Monoid (Product n) where 
instance Num n => Monoid (Product n) where 

−  mempty = 
+  mempty = Product 1 
−  mappend (Sum x) (Sum y) = Sum (x * y) 

</haskell> 
</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>. 
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? == 
+  === 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 nonequality 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 
+  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 nonequality 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> 
<haskell> 

Line 66:  Line 87:  
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts. 
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts. 

+  
+  == In more depth == 

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

+  
+  <haskell> 

+  mempty = mconcat [] 

⚫  
+  </haskell> 

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

+  
+  <haskell> 

+  mconcat [x] = x 

+  mconcat (map mconcat xss) = mconcat (concat xss) 

+  </haskell> 

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

+  
+  ==== Categorical diversion ==== 

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

+  
+  <haskell> 

+  mconcat . return = id 

+  mconcat . map mconcat = mconcat . join 

+  </haskell> 

+  
+  In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad. 

+  
+  === On the Writer monad === 

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

+  
+  <haskell> 

+  (w,x) >>= f = 

+  case f x of 

+  (v, y) > (w <> v, y) 

+  </haskell> 

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

+  
+  You might, however, wonder if there's not some other way to get a lawabiding monad. The answer is essentially no: if <hask>(w,a)</hask> is a monad, you can use its monad instance to write a monoid instance for <hask>w</hask>: basically <hask>mempty = fst (return ())</hask> and <hask>mappend x y = fst (join (x,(y,()))</hask>, and the monad laws ensure associativity and identity. So in fact, monoids are exactly what you need to make a monad structure on tuples. 

+  
+  === On the Const applicative === 

+  
+  Even more straightforwardly, <hask>Const m</hask> is applicative precisely when <hask>m</hask> is a monoid. 

== See also == 
== See also == 

+  * [http://sigfpe.blogspot.com/2009/01/haskellmonoidsandtheiruses.html Haskell Monoids and their Uses] 

−  The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.: 

−  * 
+  * [http://apfelmus.nfshost.com/monoidfingertree.html Monoids and Finger Trees] 
−  * The blog article [http://apfelmus.nfshost.com/monoidfingertree.html Monoids and Finger Trees] 

* [http://haskell.org/sitewiki/images/6/6a/TMRIssue11.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/TMRIssue11.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: 

−  * [ 
+  * [https://homepages.inf.ed.ac.uk/cheunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids] (PDF) 
Latest revision as of 02:30, 27 December 2019
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.
The basics
Declaration
class Semigroup m where
(<>) :: m > m > m
 defining sconcat is unnecessary, it has a default implementation
sconcat :: NonEmpty m > m
sconcat = ...
 defining stimes is unnecessary, it has a default implementation
stimes :: Integral a => a > m > m
stimes = ...
infixr 6 <>
class Semigroup m => Monoid m where
mempty :: m
 defining mappend is unnecessary, it copies from Semigroup
mappend :: m > m > m
mappend = (<>)
 defining mconcat is optional, since it has the following default:
mconcat :: [m] > m
mconcat = foldr mappend mempty
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 Semigroup [a] where
(<>) = (++)
instance Monoid [a] where
mempty = []
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 => Semigroup (Sum n) where
Sum x <> Sum y = Sum (x + y)
instance Num n => Monoid (Sum n) where
mempty = Sum 0
newtype Product n = Product n
instance Num n => Semigroup (Product n) where
Product x <> Product y = Product (x * y)
instance Num n => Monoid (Product n) where
mempty = Product 1
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 nonequality 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.
In more depth
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.
Categorical diversion
Note that the above two laws can also be phrased as follows:
mconcat . return = id
mconcat . map mconcat = mconcat . join
In category theory terms, this is exactly the condition for mconcat
to be a monad algebra for the list monad.
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.
You might, however, wonder if there's not some other way to get a lawabiding monad. The answer is essentially no: if (w,a)
is a monad, you can use its monad instance to write a monoid instance for w
: basically mempty = fst (return ())
and mappend x y = fst (join (x,(y,()))
, and the monad laws ensure associativity and identity. So in fact, monoids are exactly what you need to make a monad structure on tuples.
On the Const applicative
Even more straightforwardly, Const m
is applicative precisely when m
is a monoid.
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: