Encoding Free Groups

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]
cancelInverses x [] = [x]
cancelInverses x rest@(y:ys) = case (x, y) of
  (Inverse 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:

main = print . reduceFreeGroup $ FreeGroup
  [ 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.