Monoids

This little chapter is a pale shadow of Miss Monoid's lectures, but we'll do it our rough-and-ready way. A monoid is an abstraction equipped with an associative operation and an identity element. Associativity lets us split work into parts and group the results in different ways without changing the order of the data — hence parallel aggregation (map-reduce) and folds.

In Haskell, a monoid is represented by a pair of type classes: Semigroup provides an associative operation, and Monoid adds an identity element:

class Semigroup a where
  (<>) :: a -> a -> a          -- associative operation

class Semigroup a => Monoid a where
  mempty :: a                  -- identity element

Instances must obey two laws: associativity of the operation and the identity laws for $\mathtt{mempty}$:

(x <> y) <> z == x <> (y <> z)   -- associativity

mempty <> x == x                 -- left identity
x <> mempty == x                 -- right identity

The standard library provides many instances:

-- lists: (<>) = (++), mempty = []
[1, 2] <> [3]                    -- [1, 2, 3]

-- numbers form a monoid in two ways, hence the wrappers:
Sum 2     <> Sum 3               -- Sum 5      (mempty = Sum 0)
Product 2 <> Product 3           -- Product 6  (mempty = Product 1)

-- booleans:
Any True <> Any False            -- Any True   (||, mempty = Any False)
All True <> All False            -- All False  (&&, mempty = All True)

-- minimum and maximum:
Min 5 <> Min 2                   -- Min 2
Max 5 <> Max 2                   -- Max 5

Now a few words about reduce: $\mathtt{mconcat}$ is its monoidal variant. It folds a list of monoidal values without knowing anything about the concrete type:

mconcat :: Monoid a => [a] -> a
mconcat = foldr (<>) mempty

mconcat [[1], [2, 3], []]        -- [1, 2, 3]

The Monoid laws let us safely split data into parts, process those parts in parallel, and then combine the partial results with (<>) while preserving the original order.

For example, each worker can independently accumulate its own piece of a log, after which the pieces are concatenated as lists. In the same way, we can sum separate chunks of data in parallel and then add the partial sums:

-- logs from three independent workers
workerLogs = ["worker 1: done\n", "worker 2: done\n", "worker 3: done\n"]
fullLog = mconcat workerLogs

-- sums computed independently for separate chunks of data
partialSums = [Sum 120, Sum 95, Sum 143]
total = getSum (mconcat partialSums)  -- 358

Associativity guarantees that the result does not depend on how the partial results are grouped: from left to right, pairwise as a tree, or according to the number of available cores.