Group Theory in Haskell

Let's start with \(X = \{0, 1, 2\}\), the three-element set. To represent an invertible function, we can just make a two-row table like this:

\[\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\]

The permutation notation takes the set \(X\) as the first row, and then the set \(f(X)\) as the second row:

\[\begin{pmatrix} x_0 & ... & x_n \\ f(x_0) & ... & f(x_n) \\ \end{pmatrix}\]

Another name used for the Symmetric group on an n-element set is \(S_n\). The group operation for \(S_3\) is function composition, so as an example,

\[\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\circ\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ \end{pmatrix}\]

The \(\begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ \end{pmatrix}\) element is the identity, since it takes each element of \(X\) to itself.

Notice in 3.1.1 what the \(\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{pmatrix}\) element is doing. It is swapping 0 and 1. This is a transposition, whic means it swaps two elements. In cycle notation it would be \((0 \space 1)\).

If you chain together transpositions \((0\space 1)\) and \((1\space 2)\) you get longer cycles (by convention I am dropping the \(\circ\) and just juxtaposing the elements):

\[(0 \space 1)(1\space 2) = (0\space 1 \space 2)\]

The cycle notation is more compact, but harder to implement in code. We will do both in the next section to demonstrate how to implement different notations on Haskell's algebraic type system.

Now let's implement \(S_3\) in Haskell and make it easy to interactively work with at the REPL.

We can enumerate all X values using [Zero ..] Then we need to generate all \(n!\) permutations of that list, then we can zip them together and generate the (x, f x) pairs in that way.

import Data.Group.Permutation
import Data.List

data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show)

-- pmatrix notation
pmn :: Permutation X -> String
pmn p = "\\begin{pmatrix}" ++
  (concat $ intersperse " & " $ map (show . fromEnum) xs) ++ "\\\\" ++
  (concat $ intersperse " & " $ map (show . fromEnum . to) xs) ++ "\\end{pmatrix}"
  where (to, _) = pairwise p
        xs = [Zero, One, Two]

-- show permutations in the notation above
instance Show (Permutation X) where
  show p = pmn p

-- Defining the elements of S₃
s0 = permute id id          -- identity permutation
s1 = permute zo zo where  -- transpose Zero/One
  zo = (\x -> case x of
                Zero -> One
                One -> Zero
                Two -> Two)

The string output of show s1 looks like this: \begin{pmatrix}0 & 1 & 2\\1 & 0 & 2\end{pmatrix} which renders as:

\[\begin{pmatrix}0 & 1 & 2\\1 & 0 & 2\end{pmatrix}\]

This is an alternative show function that uses cycle notation. The problem in Haskell is collecting all the cycles. Consider our \(S_3\) example so far, notice how \((0 \space 1)\) is a transposition, which is also a 2-cycle. It turns out that we can prove that all permutations can be decomposed into transpositions. (Proof: 5.3.1)

An example of decomposing a permutation into transpositions is the 3-cycle: \((0 \space 1 \space 2) = (1 \space 2)(0 \space 1)\)

Think about it using function composition, the rightmost function maps \(0\) to \(1\), then the next one sends \(1\) to \(2\). So we need a generic algorithm for generating the cycle notation for a general Permutation X.

One way to do it is to define a cycle set, and observe that the cycle sets will be disjoint, and that they will partition the set \(X\).

1. Take an element \(x_1 \in X\)
2. Define the cycle set of \(x_1\) as \(\{x_1, f(x_1), f(f(x_1)), ..., f^n(x_1)\}\)
3. Take the collection of cycle sets for all elements \(x_i\). This partitions \(X\)
4. Display the sets as cycles in the output: (x1 f(x1) f(f(x1)) ... f(f(...f(x1))))

import Data.Group.Permutation
import Data.List (take)
import Data.Set (fromList)

data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show)

-- cyclesets take a perm to from and an x and then compute [x, to(x), to(to(x),...)..]
cycleset p x = fromList $ (take 3 $ iterate f x)
  where (f, _) = pairwise p

-- cycle notation
pmc :: Permutation X -> String
pmc p = show p

-- Defining the elements of S₃
s0 = permute id id        -- identity permutation
s1 = permute zo zo where  -- transpose Zero/One
  zo = (\x -> case x of
           Zero -> One
           One -> Zero
           Two -> Two)

Hask is the Category of all Haskell types. The objects of Hask are Haskell types, and the morphisms between the types are Haskell functions. The green \(\color{green}{F}\) is a functor that maps Haskell types to the set of their values.

You can also define \((\mathbb{N}, \leq)\) as a poset category, where the objects are natural numbers, the morphisms are the less than or equal to relation, and then the cardinality of finite sets can be represented as a functor from Set to this poset category. Here we define the Countable typeclass to implement the "cardinality" of a type. The implementation will compute \(|\color{green}{F}(X)|\)

Then finish by introducing Countable typeclass to get the cardinality

Bubble sort exists. Think about it. QED.

./perms.hs is a literate program that this org-mode document produces. Supporting code to make the file compile and run is defined down here in the appendix.

{-# LANGUAGE FlexibleInstances #-}
module Main where

import Data.Group.Permutation
import Data.List

data X = Zero | One | Two deriving (Bounded, Enum, Eq, Show)

-- pmatrix notation
pmn :: Permutation X -> String
pmn p = "\\begin{pmatrix}" ++
  (concat $ intersperse " & " $ map (show . fromEnum) xs) ++ "\\\\" ++
  (concat $ intersperse " & " $ map (show . fromEnum . to) xs) ++ "\\end{pmatrix}"
  where (to, _) = pairwise p
        xs = [Zero, One, Two]

-- show permutations in the notation above
instance Show (Permutation X) where
  show p = pmn p

-- Defining the elements of S₃
s0 = permute id id          -- identity permutation
s1 = permute zo zo where  -- transpose Zero/One
  zo = (\x -> case x of
                Zero -> One
                One -> Zero
                Two -> Two)

main :: IO ()
main = do
  print s1