The Free Monoid

A Monoid is a simple mathematical structure, it comprises of a type T , a function (<>) :: T -> T -> Tand a distinguished element zero :: T that satisfies two properties:

1. (<>) is associative, that means that for every a :: T , b :: T , c :: T, the following holds (a <> b) <> c = a <> (b <> c). In other words, in an expression a <> b <> c , it doesn’t matter how we choose to put our parenthesis.
2. zero :: T is an identity for (<>). That is, for any a :: T, we can combine it with zero and we get a back.
   In a formula: a <> zero = a and zero <> a = a for every a :: T.

There are a number of useful monoids in everyday life, some of them being:

• Int with (<>) = (+), zero = 0 (addition)
• Int with (<>) = (*), zero = 1 (multiplication)
• For any type a, functions a -> a form a monoid with (<>) = (.), zero = id (function composition, identity function)

A natural question that can arise is “Given any type, can I somehow turn it into a monoid in a sensible way?”

To answer that, let’s check what we need: a zero and a binary operation (<>).

Given that we know nothing about the type we might be dealing with (we don’t even know if it has any elements), we’ll have to create a new type constructor which we’ll call FreeMonoid1, and we want that for any type t, FreeMonoid1 t be a monoid.

The first thing we’ll do is say that this type contains a zero:
data FreeMonoid1 t = Zero | ...

Next, we need to represent expressions of the form a, for any a :: T, and a <> b. So we add those two constructors:

First attempt at writing a free monoid.

But this has a problem! We’re representing (a <> b) <> c in a different way than a <> (b <> c) (try to write how those two expressions look in our FreeMonoid1 type), which would break associativity!

To solve this, let’s arbitrarily choose right nesting of parenthesis for our representation, that is, every expression of the form a <> b <> c <> d will be represented as a <> (b <> (c <> d))). And finally, instead of adding a constructor for single values, we can represent those as a <> Zero, since by monoid laws, that must be the same as a!

Finally, we reach our type

data FreeMonoid t
  = Zero
  | Combine t (FreeMonoid t)

We can finally write our monoid functions for our type:

zero :: FreeMonoid t
zero = Zero

(<>) :: FreeMonoid t -> FreeMonoid t -> FreeMonoid t
Zero <> x = x -- Left identity
x    <> Zero = x -- Right identity
(Combine t1 rest1) <> x =
  -- `(a <> b) <> x` is represented as `a <> (b <> x)`
  Combine t1 (rest1 <> x)

It’s left as an exercise to check that the monoid laws actually hold for this datatype.

Now comes an idea that pops up frequently with “Free” constructions as this one: we’re taking any type and representing expressions of the form a <> (b <> zero) as data (a 'Combine' (b 'Combine' Zero)).

Can we actually interpret this with a real monoidal operation and zero and get a result?

For this, we’d need to provide a value to use as our monoidal zero and a function to use as our monoidal combine, (<>).

So we write our interpret function:

interpret :: b -> (a -> b -> b) -> FreeMonoid a -> b
interpret myZero myCombine Zero = myZero
interpret myZero myCombine (Combine a rest) =
  a `myCombine` (interpret myZero myCombine rest) -- a `Combine` (b `Combine` Zero) -> a `myCombine` (b `myCombine` myZero)

This allows us to pass such an expression as data, without forcing one to prematurely choose the way to combine the elements, here’s an example:

Suppose we are deciding how to greet an user based on wether he’s an Admin, a Power User or a regular User. The criteria to decide this is as follows: An admin has special permissions to access every feature of the app. A power user has at least one special permission, and finally, a regular User has no special permissions.

We then represent those permissions as a FreeMonoid (String, Bool) where (perm, True) indicates that the user has permission perm and False indicates the contrary.

We can now write our functions as

Interpreting a FreeMonoid

isAdmin :: FreeMonoid (String, Bool) -> Bool
isAdmin perms = interpret True (\(_, perm) rest -> perm && rest) perms

isPowerUser :: FreeMonoid (String, Bool) -> Bool
isPowerUser perms = interpret False (\(_, perm) rest -> perm || rest) perms

isRegularUser :: FreeMonoid (String, Bool) -> Bool
isRegularUser perms = not (isPowerUser perms)

The avid reader will have recognised that FreeMonoid t is simply a list of t’s: [t]!

• Zero is the empty list []
• Combine t rest is t : rest
• interpret is just foldr!

This reveals the monoidal nature of lists, it’s in a sense, the simplest monoidal structure!

Finally, understanding the techniques used here (“I want to make my type into a Monoid/Applicative/Monad, what’s the minimum structure I need to add to achieve that?”) is crucial for understanding widely used constructs such as the Free Applicative and the Free Monad.

Further reading:

• https://en.wikipedia.org/wiki/Free_monoid
• https://wiki.haskell.org/Monoid
• http://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Foldable.html#t:Foldable