Monoids, monoids everywhere

While lecture 7 of CIS194 was named Folds and Monoids, the focus was on monoids (folds had been covered earlier). While the wikipedia page might look overwhelming on a first sight, monoids can be tackled with some reading and practice.

Speaking of reading, this lecture linked to some really interesting articles showing what one can apply monoids to. Reading through them will probably give you a lot better explanation what I can write down here.

The whole thing boils down to few rules that state that there’s a set (like all integers, conveniently presented as Integer type), a binary function (for example sum in case of Integer) and unit or empty value (0 in our example). Unit is chosen so that the function applied to any value and unit, will produce that any value (1 + 0 = 1, 2 + 0 = 2, 0 + 5 = 5, etc.).

The binary function is associative. In other words, when there are several applications of that function, it doesn’t matter in which order they are done: 1 + (2 + 3) = (1 + 2) + 3. Don’t mix this with commutative property, like I did originally.

This isn’t the only way define monoid for integers. One can also select 1 as unit and product as the function and same laws still hold.

But what can one do with such a thing and what does it look like in Haskell? Since there are (at least) two ways to define monoid for integers, Haskell has defined new types for them Sum and Product:

> import Data.Monoid
> Sum 2 <> Sum 4
Sum {getSum = 6}
> Product 2 <> Product 4
Product {getProduct = 8}

So one can combine two integers either by adding or multiplying them (<> or the diamond operator is the binary operator used to combine them).

The task in exercise was to define some basic operations for binary tree that had been defined as:

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
  deriving (Eq, Show)

m is used to store metadata about the node, while a is the actual data. One can represent strings neatly with this system, having m to store size of the tree (retrieved with tagSize function) and a as letter. This way searching for a specific index is very fast (provided that the tree is balanced).

indexJ :: (Sized b, Monoid b) =>
          Int -> JoinList b a -> Maybe a
indexJ 0 (Single _ a) = Just a
indexJ n (Append _ l r)
                     | tagSize l > n = indexJ n l
                     | otherwise     = indexJ (n - tagSize l) r
indexJ _ _ = Nothing

And how does one get size of the tree neatly? By storing Add 1 in Single node and combining meta info from subtrees in case of Append. For that a new operator +++ was to defined:

(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
(+++) Empty p = p
(+++) p Empty = p
(+++) l r = Append (tag l <> tag r) l r

Looking at this, I started thinking that this looks awfully like a monoid. There’s binary function that combines two JoinList in associative way and there’s unit. We can make monoid out of this by writing:

instance Monoid m => Monoid (JoinList m a) where
  mempty = Empty
  mappend a b = a +++ b

Now two JoinLists can be combined using diamond operator and the metadata in m is also combined with correct diamond operator. How nifty is that? The resulting tree isn’t necessarily balanced though, but one could write a function to do that too.

Other tasks included implementing dropJ and takeJ that work just like their regular counterparts drop and take.

Really funny trick is that since pair of monoids is a monoid too, one can store arbitrarily large amount of metadata in m (as long as it’s in form of monoids) and routines above continue working. In the exercise task was to write pair of monoids that tracks both size of the tree (lines in file) and combined scrabble score of it, same time allowing browsing and editing the file (indexJ, takeJ and dropJ were useful here).

So to recap, monoid is just a name for a specific pattern that occurs often in programs. When programmer recognizes it, they can replace it with abstraction, yielding more general function. Knowing the name of the pattern makes communication between programmers easier, because they can speak a common language (provided that everyone has same understanding of the term of course).