In math, “free” loosely means that we can come up with some structure based on some other structure without needing extra information. That is, there is a general method of taking the first structure and adding something more to it. One combination of structures we can do this for is sets and groups: for a set, there’s a corresponding free group. We don’t need to know anything about the set to do this—the extra group is free!
Let’s call the set \(S\) and the group we’re trying to create \(G\). We’ll also need to make another set which we can call \(\bar{S}\). This second set will have “inverses” of the elements in \(S\). However, we can’t say much more than that, because we’re not allowed to peek inside \(S\) if we want \(G\) to truly be free. So let’s just say that \(\bar{S}\) is isomorphic to and disjoint from \(S\), and has these “inverses” of each element in \(S\).
I’m going to gloss over most of the math, and talk mainly about how we might encode free groups in Haskell. We can encode inverses like this:
data WithInverse a = Element a | Inverse a
deriving Show
For every element in \(S\)
(Element a
) there’s a corresponding element in \(\bar{S}\) encoded by
Inverse a
.
The way to generate \(G\) will involve treating the elements of \(S\) like letters in a word, and then doing some reductions on that word to guarantee certain properties. If we wanted to, we could encode this notion of words like
type Word a = [WithInverse a]
However, I think the intent of [WithInverse a]
is
slightly more obvious, so that’s what I’ll use. The encoding of a free
group, then, looks like some container of a word, but we have to make
sure that word is reduced. The container bit is just creating a new
type
newtype FreeGroup a =
FreeGroup { runFreeGroup :: [WithInverse a] }
deriving Show
Now we need to code up the reduction. Let’s say we have a word like \(\bar{a}bcbb\bar{b}\bar{b}a\), where \(\bar{x}\) is the inverse of \(x\), drawn from \(\bar{S}\).
The word reduction procedure scans through the word. Every time it finds a complementary pair of letters next to each other (either \(x\bar{x}\) or \(\bar{x}x\)), that pair gets canceled out. For example, \(a\bar{b}b\bar{a}\) reduces to \(a\bar{a}\) after canceling out the \(b\)s, and then to the empty word after canceling \(a\)s. Our main example word \(\bar{a}bcbb\bar{b}\bar{b}a\) reduces to \(\bar{a}bca\) in the same way.
Taking this into consideration, we have a fold over a word that looks for adjacent pairs of inverses to cancel, and eventually builds a newly reduced word. This could be written like this:
reduceFreeGroup :: Eq a => FreeGroup a -> FreeGroup a
=
reduceFreeGroup FreeGroup . foldr cancelInverses [] . runFreeGroup
cancelInverses :: Eq a =>
WithInverse a -> [WithInverse a] -> [WithInverse a]
= [x]
cancelInverses x [] @(y:ys) = case (x, y) of
cancelInverses x restInverse x, Element y) | x == y -> ys
(Element x, Inverse y) | x == y -> ys
(-> x : rest _
We can test that this reduction actually works for our example word by running this:
= print . reduceFreeGroup $ FreeGroup
main Inverse 'a'
[ Element 'b'
, Element 'c'
, Element 'b'
, Element 'b'
, Inverse 'b'
, Inverse 'b'
, Element 'a'
, ]
In fact, this does produce
FreeGroup {runFreeGroup = [Inverse 'a',Element 'b',Element 'c',Element 'a']}
,
so it looks like it’s working.
Of course, this isn’t the best or only way to encode free groups. For
example, runtime could probably be improved by using better data
structures, like difference lists. It’s possible to extend our current
implementation by coming up with Functor
,
Applicative
, and Monad
instances for
FreeGroup
. I just often find it worthwhile to try to come
up with a working implementation in code for mathematical ideas—it’s a
nice check that I have some baseline understanding about how they
work.