Haskell/Monoids
This page is a stub. You can help Haskell by expanding it. 
In earlier parts of the book, we have made a few passing allusions to monoids and the Monoid
type class (most notably when discussing MonadPlus). Now it is time to give them a more detailed look, and show what makes them useful.
Introduction[edit]
A monoid (m, mappend, mempty) is a type m together with an associative operation mappend :: m > m > m (also called (<>) in Haskell) that combines two elements and a zero element mempty :: m which is the neutral element of mappend: Before describing them more formally let's see monoids in action.
Examples[edit]
As an information introduction, let's take a look at a common pattern:
> (5 + 6) + 10 == 5 + (6 + 10) True > (5 * 6) * 10 == 5 * (6 * 10) True > ("Hello" ++ " ") ++ "world!" == "Hello" ++ (" " ++ "world!") True
This property is called associativity and doesn't just hold for those selected values but for all integers under addition, all integers under multiplication and all lists under concatenation, let's look at a few more examples:
> 255 + 0 == 255 && 0 + 255 == 255 True > 255 * 1 == 255 && 1 * 255 == 255 True > [1,2,3] ++ [] == [1,2,3] && [] ++ [1,2,3] == [1,2,3] True
Here 0 is the identity element when adding integers, 1 is the identity when multiplying them and [] is the identity when appending two lists: This should not surprise you. At this point you may have realised the connection.
 Integers form a monoid under addition where 0 is the unit: (Integer, (+), 0)
 Integers form a monoid under multiplication where 1 is the unit: (Integer, (*), 1)
 Lists form a monoid under concatenation: ([a], (++), [])
Since Integers form monoids under two distinct operations we instead create two new datatypes: Sum for addition and Product for multiplication.
> import Data.Monoid > Sum 5 <> Sum 6 <> Sum 10 Sum {getSum = 21} > mconcat [Sum 5, Sum 6, Sum 10] Sum {getSum = 21} > getSum $ mconcat $ map Sum [5, 6, 10] 21 > getProduct $ mconcat $ map Product [5, 6, 10] 300 > mconcat ["5", "6", "10"] "5610"
But how is this useful?
Generalizing functions[edit]
We can generalize a function that concatenates three lists:
threeConcat :: [a] > [a] > [a] > [a] threeConcat a b c = a ++ b ++ c
with:
threeConcat' :: Monoid m => m > m > m > m threeConcat' a b c = a <> b <> c  > threeConcat' "Hello" " " "world!"  "Hello world!"  > threeConcat' (Sum 5) (Sum 6) (Sum 10)  Sum {getSum = 21}
Other functions like fold :: (Foldable t, Monoid m) => t m > m from Data.Foldable use properties of monoids to reduce any foldable structure containing monoids into a single monoidal value:
> fold ["Hello", " ", "world!"] "Hello world!" > fold (Just (Sum 10)) Sum {getSum = 10} > fold Nothing :: Sum Integer Sum {getSum = 0}
This way if we create our own container (like trees) containing our own monoidal data type, we can immediately make use of previously defined functions like fold!
Exercises 


Haskell definition and laws[edit]
The Monoid
type class (from Data.Monoid) captures this general concept:
class Monoid a where mempty :: a mappend :: a > a > a mconcat :: [a] > a mconcat = foldr mappend mempty
and lists are defined as:
instance Monoid [a] where mempty = [] mappend = (++)
and the third method mconcat is provided as bonus with a default implementation of mconcat = foldr (++) []
which is equivalent to concat
for lists.
It is legitimate to think of monoids as types which support appending, though some poetic license with respect to what is meant by "appending" is advisable, as the Monoid
definition is extremely generic and not at all limited to data structures. Integer numbers, for instance, form a monoid with addition as "appending" and 0 as, well, zero:
  Monoid under addition. newtype Sum a = Sum { getSum :: a }   Monoid under multiplication. newtype Product a = Product { getProduct :: a } instance Num a => Monoid (Sum a) where mempty = Sum 0 Sum x `mappend` Sum y = Sum (x + y) instance Num a => Monoid (Product a) where mempty = Product 1 Product x `mappend` Product y = Product (x * y)
Monoids also have laws, which the instances of Monoid
must follow. They are really simple, though; corresponding to the neutral element and associativity properties we mentioned:
mempty <> x = x x <> mempty = x x <> (y <> z) = (x <> y) <> z
The Monoid
class is defined in Data.Monoid, along with instances for many common types.
Examples[edit]
For a class with such a pompous name, monoids might seem just too simple, or just plain boring. Do not let any such impression mislead you, though: they have many interesting applications. We will mention some of them in this section.
 The
Writer
monad  A computation of type
Writer w a
returns a value of typea
while producing accumulating output of typew
.w
is an instance ofMonoid
, and the bind operator of the monad usesmappend
to accumulate the output. It is easy to picturew
as a list type used for some kind of logging; we can use any monoid instance, though, which opens up many possibilities thanks to the generality of the class.
 The
Foldable
class Foldable
, available from Data.Foldable, provide a simple way to generalize list folding (as well as many relatedData.List
) functions to other data structures.^{[2]} The implementations inData.Foldable
take advantage of monoids by generating monoidal values from the elements of the data structure, which can then be trivially combined withmappend
. Another role of theFoldable
is in the definition of theTraversable
class (in Data.Traversable), which generalizessequence
fromControl.Monad
.
 Finger trees
 Moving on from operations on data structures to data structure implementations, monoids can be used to implement finger trees, an efficient and very versatile data structure. Its implementation makes use of monoidal values as tags for the tree nodes; and different data structures  such as sequences, priority queues and search trees  can be obtained simply by changing the involved
Monoid
instance. This blog post, based on a paper by Ralf Hinze and Ross Patterson^{[3]}, contains a brief and accessible explanation on how monoids are used in finger trees.
 Options and settings
 In a wholly different context, monoids can be a handy way of treating application options and settings. Two examples are Cabal, the Haskell packaging system ("Package databases are monoids. Configuration files are monoids. Command line flags and sets of command line flags are monoids. Package build information is a monoid."[1]) and XMonad, a tiling window manager implemented in Haskell ("xmonad configuration hooks are monoidal."[2]).
Homomorphisms[edit]
This section is a stub. You can help Wikibooks by expanding it. 
A function f :: a > b
between two monoids a
and b
is called a homomorphism if it preserves the monoid structure, so that:
f mempty = mempty f (x `mappend` y) = f x `mappend` f y
For instance, length
is an homomorphism between ([],++) and (Int,+)
length [] = 0 length (xs ++ ys) = length x + length y
An interesting example "in the wild" of monoids and homomorphisms was identified by Chris Kuklewicz amidst the Google Protocol Buffers API documentation. Based on the quotes provided in the referenced comment, we highlight that the property that
MyMessage message; message.ParseFromString(str1 + str2);
is equivalent to
MyMessage message, message2; message.ParseFromString(str1); message2.ParseFromString(str2); message.MergeFrom(message2);
means that ParseFromString
is a homomorphism. Translating it to Haskell and monoids, the following equations hold:
parse :: String > Message  these are just equations, not actual code. parse [] = mempty parse (xs ++ ys) = parse xs `merge` parse ys
Well, it doesn't hold perfectly, because parse can fail, but roughly so.
Further reading[edit]
 Dan Pipone (Sigfpe) on monoids: a blog post overview; a comment about intuition on associativity.
 Additional comment on finger trees: FingerTrees.
Notes[edit]
 ↑ If you check the documentation for
Data.Monoid
, you will find that both instances are defined for types inNum
, through the means of twonewtype
wrappers.  ↑ Note that this kind of folding is different from the one discussed in Haskell/Other data structures.
 ↑ Ralf Hinze and Ross Paterson. Finger Trees: A Simple Generalpurpose Data Structure. Journal of Functional Programming 16, 2 (2006), pages 197217.