Last modified on 13 May 2014, at 17:44

Haskell/Monoids

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). Here we'll give them a more detailed look and show what makes them useful.

IntroductionEdit

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.

ExamplesEdit

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 it doesn't hold for only those selected values but for all integers under addition, all integers under multiplication, and all lists under concatenation.

Here's another type of pattern:

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

So:

  • 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 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 functionsEdit

Take a function that concatenates three lists:

threeConcat :: [a] -> [a] -> [a] -> [a]
threeConcat a b c = a ++ b ++ c

We can generalize this function to work with any monoid:

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
  1. There is a second possible instance of Monoid for Integer using multiplication instead of addition as the combining operation. Implement that instance.[1]
  2. It is possible to define mempty and mappend in terms of mconcat. Write the definition of this. Figure out whether or not your definition automatically fullfills the above laws.

Haskell definition and lawsEdit

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

The third method mconcat is provided as bonus with a default implementation of mconcat = foldr (++) [] which is equivalent to concat for lists.

Lists are defined as:

instance Monoid [a] where
    mempty  = []
    mappend = (++)

It is legitimate to think of monoids as types which support appending (though some poetic license is required as the Monoid definition is extremely generic and not at all limited to data structures, so "appending" seems metaphoric in some cases). 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)

The laws which all instances of Monoid must follow 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.

ExamplesEdit

For a class with such a pompous name, monoids might seem plain and boring. Do not let any such impression mislead you; they have many interesting applications.

The Writer monad 
A computation of type Writer w a returns a value of type a while producing accumulating output of type w. w is an instance of Monoid, and the bind operator of the monad uses mappend to accumulate the output. It is easy to picture w 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, provides a simple way to generalize list folding (as well as many related Data.List) functions to other data structures.[2] The implementations in Data.Foldable take advantage of monoids by generating monoidal values from the elements of the data structure, which can then be trivially combined with mappend. Another role of the Foldable is in the definition of the Traversable class (in Data.Traversable), which generalizes sequence from Control.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 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.[3]
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]).

HomomorphismsEdit

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 (in Python)

    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 readingEdit

  • Additional comments on Monoid usage in Cabal: [3]; [4].


NotesEdit

  1. If you check the documentation for Data.Monoid, you will find that both instances are defined for types in Num, through the means of two newtype wrappers.
  2. Note that this kind of folding is different from the one discussed in Haskell/Other data structures.
  3. This blog post, based on a paper by Ralf Hinze and Ross PattersonRalf Hinze and Ross Paterson, contains a brief and accessible explanation on how monoids are used in finger trees.