Monoids

```-- strings with con­cate­na­tion

("foo" ++ "bar") ++ "baz" -- foo­bar­baz
"foo" ++ ("bar" ++ "baz") -- foo­bar­baz
"" ++ "foo" -- foo

(2 + 3) + 4 -- 9
2 + (3 + 4) -- 9
0 + 100 -- 100

-- num­bers with mul­ti­pli­ca­tion

(2 * 3) * 4 -- 24
2 * (3 * 4) -- 24
1 * 100 -- 100

-- lists with append

([1, 2] ++ [3, 4]) ++ [5, 6] -- [1, 2, 3, 4, 5, 6]
[1, 2] ++ ([3, 4] ++ [5, 6]) -- [1, 2, 3, 4, 5, 6]
[] ++ [1, 2, 3] -- [1, 2, 3]

-- booleans with or

(True or True) or False -- True
True or (True or False) -- True
False or True -- True

-- booleans with and

(True and True) and False -- False
True and (True and False) -- False
True and False -- False
```

The Laws

If you were to dis­till down the sim­i­lar­i­ties between all those exam­ples, what would we have? For all `x`, `y`, `z` of the same type:

• There exists an asso­cia­tive oper­a­tor we’ll call `map­pend`.If you sur­round a func­tion name with ` it becomes an infix oper­a­tor. These are back­ticks, not sin­gle quotes!

```(x `map­pend` y) `map­pend` z = x `map­pend` (y `map­pend` z)
```
• There exists an iden­tity ele­ment we’ll call `mempty`.

```mempty `map­pend` x = x `map­pend` mempty = x
```

All of the exam­ples above sat­isfy these two laws. Any data that sat­is­fies the above laws is cal­lend a monoid.This is the Offi­cial Math Name™, but it’s the exact same thing as com­bin­able from your home­work. When we speak of a type being a monoid, it must be with respect to a par­tic­u­lar oper­a­tor. For exam­ple, inte­gers are a monoid with respect to addi­tion, but not sub­trac­tion. A type can be a monoid with respect to many dif­fer­ent oper­a­tors, as booleans above are with both con­junc­tion and dis­junc­tion.

The Typeclass

We can define a type­class for monoids.

```class Monoid m where
mempty :: m
map­pend :: m -> m -> m
mcon­cat :: [m] -> m
mcon­cat = foldr map­pend mempty
```

So, in order to make a type an instance of `Monoid` you have to pro­vide an `mempty` value and an `map­pend`You can use the infix oper­a­tor `<>` instead of `map­pend`. func­tion. You get `mcon­cat` for free. The fol­low­ing is an instance of `Monoid` for lists.

```instance Monoid [a] where
mempty = []
map­pend = (++)
```

Haskell does not auto­mat­i­cally check that the monoid laws hold. It is the respon­si­bil­ity of the pro­gram­mer to ver­ify that every instance of `Monoid` sat­is­fies the laws.

Fast Indexing

With fin­ger trees you can write fast purely func­tional imple­men­ta­tions of many data struc­tures includ­ing sequences, pri­or­ity queues, and search trees. They fun­da­men­tally rely on monoids.

Con­sider the hum­ble linked list. While access­ing the head is fast, the tail requires touch­ing all the ele­ments of the list. Can we do bet­ter? Sup­pose we have the fol­low­ing data struc­ture.

```data Tree v a = Leaf v a
| Branch v (Tree v a) (Tree v a)
```

This is a binary tree such that all the nodes are anno­tated with a value `v`, while all the ele­ments of type `a` are stored at the leaves.

The leaves store ele­ments from left to right. The fol­low­ing will con­struct the orig­i­nal list stored in a tree.

```to­List :: Tree v a -> [a]
to­List (Leaf _ a)     = [a]
to­List (Branch _ x y) = to­List x ++ to­List y
```

Given a `Tree` we can retrieve its anno­ta­tion eas­ily by pat­tern match­ing.

```tag :: Tree v a -> v
tag (Leaf v _)     = v
tag (Branch v _ _) = v
```

Given a tree, we want to index ele­ments from it. Get­ting the `head` is easy. We can just tra­verse to the left-most ele­ment.

```head :: Tree v a -> a
head (Leaf _ a)     = a
```

What about the oth­ers? This is where our anno­ta­tions can help. What hap­pens if every sub­tree is anno­tated with its size?

We can use these anno­ta­tions to direct our search. If the left sub­tree is larger than our index, then we know the ele­ment must be on the left side. Oth­er­wise, we know the ele­ment is in the right sub­tree. We can recurse and adjust the index as nec­es­sary.

Let’s imple­ment this idea.

```type Size = Int
```

This type will remind us what our anno­ta­tions rep­re­sent. We want the fol­low­ing invari­ant to hold across all our nodes.

```tag (Leaf ...)       = 1
tag (Branch ... x y) = (tag x) + (tag y)
```

Instead of con­struct­ing trees with their actual con­struc­tors, we can build our own smart con­struc­tors which will auto­mat­i­cally anno­tate nodes with their proper val­ues.

```leaf :: a -> Tree Size a
leaf a = Leaf 1 a

branch :: Tree Size a -> Tree Size a -> Tree Size a
branch x y = Branch ((tag x) + (tag y)) x y
```

So long as we only cre­ate trees using `leaf` and `branch`, our invari­ant will be guar­an­teed. Now we can write our index­ing func­tion `!!`.

```(!!) :: Tree Size a -> Int -> a
(Leaf _ a)      !! 0 = a
(Branch _ x y)  !! n
| n < tag x     = x !! n
| oth­er­wise     = y !! (n - tag x)
```

A Priority Queue

A pri­or­ity is a dif­fer­ent data struc­ture than returns the most “urgent” ele­ment accord­ing to its pri­or­ity. We will rep­re­sent pri­or­i­ties as inte­gers, where smaller ones are more urgent.

```type Pri­or­ity = Int
```

We recy­cle the binary tree from ear­lier. We can view this as a tour­na­ment, so every sub­tree is anno­tated with the small­est pri­or­ity it con­tains.

Like before, we need an invari­ant about our anno­ta­tions.

```tag (Leaf ...)       = pri­or­ity a
tag (Branch ... x y) = (tag x) `min` (tag y)
```

Given a tour­na­ment tree, we could retrieve the ele­ment with small­est pri­or­ity in `log n` time, assum­ing the tree is bal­anced, using a sim­i­lar tech­nique as above.

```win­ner :: Tree Pri­or­ity a -> a
win­ner t = go t
where
go (Leaf _ a)        = a
go (Branch _ x y)
| tag x == tag t = go x   -- win­ner on left
| tag y == tag t = go y   -- win­ner on right
```

The Monoid Connection

One and the same tree struc­ture can be used for two quite dif­fer­ent pur­poses, just by using dif­fer­ent anno­ta­tions. Rec­og­niz­ing that the tags form a monoid, we can unify both imple­men­ta­tions. Notice `!!` and `win­ner` are actu­ally spe­cial cases of the same func­tion.

View­ing the pre­vi­ous exam­ples through the lense of a monoid, we gen­er­al­ize our invari­ant.

```tag (Branch ... x y) = (tag x) <> (tag y)
```

The pre­vi­ous exam­ples can be recre­ated by mak­ing each anno­ta­tion an instance of `Monoid`.

```instance Monoid Size where
mempty  = 0
map­pend = (+)

instance Monoid Pri­or­ity where
mempty  = max­Bound
map­pend = min
```

Hence, we can write a uni­fied smart con­struc­tor.

```branch :: Monoid v => Tree v a -> Tree v a -> Tree v a
branch x y = Branch ((tag x) <> (tag y)) x y
```

For leaves, the tag is obtained from the ele­ment. We can cap­ture this in a type­class.

```class Monoid v => Mea­sured a v where
mea­sure :: a -> v
```

The cor­re­spond­ing smart con­struc­tor reads as fol­lows.

```leaf :: Mea­sured a v => a -> Tree v a
leaf a = Leaf (mea­sure a) a
```

For our exam­ples, we need the appro­pri­ate instances again.

```instance Mea­sured a Size where
mea­sure _ = 1            -- one ele­ment = size 1

instance Mea­sured Foo Pri­or­ity where
mea­sure a = pri­or­ity a   -- urgency of the ele­ment
```

How does the anno­ta­tion at the top of a tree relate to the ele­ments at the leaves? In our two exam­ples, it was the total num­ber of leaves and the least pri­or­ity respec­tively. These val­ues are inde­pen­dent of the actual shape of the tree. Thanks to the asso­cia­tiv­ity of `<>`, this is true for any monoid.

By asso­cia­tiv­ity, these two trees have the same anno­ta­tions.

```(v1<>v2)<>(v3<>v4) = v1<>(v2<>(v3<>v4))
```

In fact, as long as the sequences of leaves are the same, this quan­tity will be the same. The tag at the root of a tree with `n` ele­ments is

```mea­sure a1 <> mea­sure a2 <> mea­sure a3 <> ... <> mea­sure an
```

While inde­pen­dent of the shape of the branch­ing, i.e. on the place­ment of paren­the­sis, this may of course depend on the order of ele­ments. It makes sense to refer to this com­bi­na­tion of mea­sures of all ele­ments as the mea­sure of the tree.

```instance Mea­sured a v => Mea­sured (Tree a v) v where
mea­sure = tag
```

Thus, every tree is anno­tated with its mea­sure.

Search

Our efforts cul­mi­nate in the uni­fi­ca­tion of the two search algo­rithms `!!` and `win­ner`. They are cer­tainly sim­i­lar; at each node, they descend into one of the sub­trees which is cho­sen depend­ing on the anno­ta­tions. But to see their exact equiv­a­lence, we have to ignore branches and group­ing for now because this is exactly what asso­cia­tiv­ity “abstracts away.”

In a sequence of ele­ments `a1, a2, ..., an` how does one find say the third one? Well, we scan the list from left to right and add 1 for each ele­ment encoun­tered. As soon as the count exceeds 3, we have found the third ele­ment.

```1                -- is not > 3
1 + 1            -- is not > 3
1 + 1 + 1        -- is not > 3
1 + 1 + 1 + 1    -- is > 3
...
```

Sim­i­larly, how to find the ele­ment of a least pri­or­ity say `v`? Well, we can scan the list from left to right and keep track of the min­i­mum pri­or­ity so far. We have com­pleted our search once it becomes equal to `v`.

```v1                                -- still big­ger than v
v1 `min` v2                       -- still big­ger than v
v1 `min` v2 `min` v3              -- still big­ger than v
v1 `min` v2 `min` v3 `min` v4     -- equal to v!
...
```

In gen­eral terms, we are look­ing for the posi­tion where a pred­i­cate `p` switches from `False` to `True`.

```mea­sure a1                                              -- not p
mea­sure a1 <> mea­sure a2                                -- not p
mea­sure a1 <> mea­sure a2 <> mea­sure a3                  -- not p
mea­sure a1 <> mea­sure a2 <> mea­sure a3 <> mea­sure a4    -- p
...                                                     -- p
```

In other words, we are look­ing for the posi­tion k where

```p (mea­sure a1 <> ... <> mea­sure ak) = False
p (mea­sure a1 <> ... <> mea­sure ak <> mea­sure a(k + 1)) = True
```

The key point is that `p` does not test sin­gle ele­ments but com­bi­na­tions of them, and this allows us to do binary search! Namely, how to find the ele­ment where `p` flips? Divide the total mea­sure into two halves.

```x <> y
x = mea­sure a1 <> ... <> mea­sure a(n/2)
y = mea­sure a(n/2 + 1) <> ... <> mea­sure an
```

If `p` is `True` on the first half, then we have to look there for the flip, oth­er­wise we have to search the sec­ond half. In the lat­ter case, we would have to split `y = y1 <> y2` and test `p (x <> y1)`.

In the case of our data struc­tures, the tree shape deter­mines how the mea­sure is split into parts at each step.

```search :: Mea­sured a v => (v -> Bool) -> Tree v a -> Maybe a
search p t
| p (mea­sure t) = Just (go mempty p t)
| oth­er­wise     = Noth­ing
where
go i p (Leaf _ a) = a
go i p (Branch _ l r)
| p (i <> mea­sure l) = go i p l
| oth­er­wise          = go (i <> mea­sure l) p r
```

Since we have anno­tated each branch with its mea­sure, test­ing `p` takes no time at all. Of course, this algo­rithm only works if `p` really does flip from `False` to `True` exactly once. This is the case we say that `p` is a monot­o­nic pred­i­cate. Our two exam­ples `(> 3)` and `(== min­i­mum)` have this prop­erty and thus, we can finally con­clude.

```t !! k   = search (> k)
win­ner t = search (== mea­sure t)
```