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:
(<>)is associative, that means that for everya :: T,b :: T,c :: T, the following holds(a <> b) <> c = a <> (b <> c). In other words, in an expressiona <> b <> c, it doesn’t matter how we choose to put our parenthesis.zero :: Tis an identity for(<>). That is, for anya :: T, we can combine it withzeroand we getaback.
In a formula:a <> zero = aandzero <> a = afor everya :: T.
There are a number of useful monoids in everyday life, some of them being:
Intwith(<>) = (+), zero = 0(addition)Intwith(<>) = (*), zero = 1(multiplication)- For any type
a, functionsa -> aform 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]!
Zerois the empty list[]Combine t restist : restinterpretis justfoldr!
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:
