-- strings with con­cate­na­tion

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

-- num­bers with addi­tion

(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:

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­pendYou 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
head (Branch _ x _) = head x

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


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

Additional Reading