The Group Typeclass

In the previous post of this series, we showed that the permutations of a set are functions that can be inverted or composed to give rise to different permutations of the same set. Given these operations, sets of permutations form an algebraic structure called a group.

In this post, we’ll define what a group is, explore its structure, and discuss some examples of groups. We’ll use the Group typeclass and show it’s relationship to other typeclasses. We’ll also show how permutations have a group structure, and that any other group can be described by a permutation group.

An Intuition for Monoids and Groups

You might be familiar with the Semigroup or Monoid typeclasses. Even if you’re not familiar with them by these names, you’re probably very familiar with the concepts they abstract. In a broad sense monoids and semigroups allow us to combine two elements of some type to get another element of the same type. You can add numbers, concatenate strings, merge dictionaries, or compose functions. We’ll cover some examples and more formal definition in the next section.

These typeclasses are extremely useful; libraries like Spire and Algebird use them extensively for numerical and algebraic computation. But sometimes, they’re too general. A more specific abstraction can give us a greater ability to reason about the sets of elements that these combining operations act on. Groups are one such abstraction.

Groups extend monoids to allow decomposing elements. If you’ve used used operations like subtraction, division, factoring, inverting, or undo, then you’ve already worked with groups whether you realize it or not. Consider how heavily you use cancellation to solve or simplify algebraic equations. This is the kind of reasoning power that groups enable. The Group typeclass abstracts this ability, formalizing what it means to cancel out elements from a combination.

Groups are less general than monoids, since not all monoids have a group structure with an operation that can be reversed. But while we lose general applicability of our typeclass, we gain an increased ability to reason about our elements.

Semigroups and Monoids

Semigroup

A semigroup is a set with an associative binary operation. It lets you combine any two elements to get another element of the same type. It’s extremely general; instances are already defined out of the box for many different types. Here are some examples using Cats:

import cats._
import cats.implicits._

Semigroup.combine(1, 2)
// res0: Int = 3

Semigroup.combine("Group", "Theory")
// res1: String = "GroupTheory"

Semigroup.combine(Map('A' -> 10), Map('A' -> 5, 'B' -> 5))
// res2: Map[Char, Int] = Map('A' -> 15, 'B' -> 5)

Cats provides a simplified syntax that we’ll use from here on out:

1 |+| 2 |+| 3
// res4: Int = 6

"Group" |+| "Theory"
// res5: String = "GroupTheory"

Note the fact that the combining operation must be associative, which means the following equality must hold for any x, y, and z.

(x |+| y) |+| z == x |+| (y |+| z)

The operation is also not necessarily commutative; x |+| y is not necessarily equal to y |+| x:

assert(1 |+| 2 == 2 |+| 1) // true for `Int`

assert("Group" |+| "Theory" != "Theory" |+| "Group") // but not for `String`

Monoid

Monoid extends semigroup with the concept of an identity element. Combining an element with the identity results in that same element, (eg., adding zero). This is true whether combining from the left or right:

assert(0 |+| 3 == 3)

assert(3 |+| 0 == 3)

Monoid instances from Cats give us the identity element of a set via .empty:

Monoid[Int].empty
// res6: Int = 0

Monoid[String].empty
// res7: String = ""

In the context of collections, this allows reducing an arbitrary list down to a single element to give a very general definition of a sum:

Monoid[Int].combineAll(1, 2, 3, 4)
// res8: Int = 10

Addition isn’t the only way to define a monoid for integers. We could provide our own definition that uses multiplication, where the identity is 1 instead of 0:

IntProductMonoid extends Monoid[Int] {
  def empty = 1
  def combine(x: Int, y: Int) = x * y
}

IntProductMonoid.combine(3, 5)
// res9: Int = 12

(Note: both the terms “multiplication” and “addition” are used to describe the combining operator of a group, with the latter being reserved for commutative operations. We can disambiguate with “integer multiplication” and “integer addition”, but in this post, we’ll follow Cats and use the the more neutral term, “combination”, denoted |+|)

(Note that without the identity element, we wouldn’t be able to reduce an empty list. eg., in folds, we would have to provide a default case.)

Semigroups and Monoids are both already well-documented in Cats’ page on Type-Classes.

Group: Monoid with Inverse

As monoids extend semigroups with identity elements, groups extend monoids with the concept of inverse elements.

A group requires that every element has a unique inverse. You can combine an element with its inverse to “cancel out” to the identity element. While it’s not as heavily used or documented, Cats does provide a definition. The Group[A] typeclass includes an additional method, def inverse(a: A): A, that maps each element to its inverse. It essentially looks like this:

trait Group[A] {
  def empty: A // identity
  def inverse(a: A): A
  def combine(a: A, b: A): A
}

Cats provides instances out of the box for various numerical types. They can be used like so:

scala> Group[Int].inverse(1)
res0: Int = -1

scala> Group[Int].remove(10, 1)
res1: Int = 9

The existence of inverse elements allows us to implement remove which is the inverse operation to combine. It’s analogous to subtraction, where subtracting b from a really just means adding negative b to a. Removing means combining inverse b with a:

def remove(a: A, b: A): A = combine(a, inverse(b))

Cats also provides an operator syntax for remove that’s reminiscent of subtraction:

scala> 10 |-| 1
res2: Int = 9

scala> 3 |+| 2 |-| 2
res3: Int = 3

Note that our integer multiplication monoid from above isn’t also a group given division, since the inverses (reciprocal fractions) are no longer integers. To form a group with multiplication, we’d need rational numbers or some sort of Fraction type. Floating point division doesn’t quite work here because of rounding. Since the mapping isn’t one-to-one. We get in trouble when we assume it works like a true inverse. In the following example, if division truly gave you the inverse, multiplication and division by 3.0 would cancel out, and we’d get 0.1:

scala> 0.1 * 3.0 / 3.0
res0: Double = 0.10000000000000002

So a group is a monoid with a inverses. This sounds simple, but it actually implies a lot of structure and laws for the set of A, especially when the type is inhabited by a finite number of elements, or the operation is non-commutative.

To understand some of this structure, we’ll need to discuss permutations. If you aren’t already familiar with permutations, and specifically how a permutation is actually a bijective function, go back and read this post before continuing on.

Permutation Groups

Every element of a group can be viewed as a permutation. To illustrate this, we’ll need an example of a small finite group. We’ll use the integers modulo 6 under addition:

case class Mod6 private(value: Int) 

object Mod6 {
  def apply(n: Int) = {
    val mod6 = n % 6
    if (mod6 >= 0) new Mod6(mod6)
    else new Mod6(mod6 + 6)
  }

  implicit object Mod6Group extends Group[Mod6] {
    override def empty = Mod6(0)
    override def inverse(n: Mod6) = apply(-n.value)
    override def combine(m: Mod6, n: Mod6) = apply(n.value + m.value)
  }
}

With this implementation, there are only 6 ways to construct an valid instance of Mod6 using our apply method. In formal terms, the Mod6 group has order 6:

scala> val elements = (-12 to 12).map(Mod6(_)).distinct.toList
elements: List[Mod6] = List(Mod6(0), Mod6(1), Mod6(2), Mod6(3), Mod6(4), Mod6(5))

We can map over all these elements to get a “combination table” of sorts (Analogous to multiplication tables):

scala> val mod6Table = elements.map(m => elements.map(m |+| _))
mod6Table: List[List[Mod6]] = ...

scala> mod6Table.map(_.map(_.value).mkString(" ")) foreach println
0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4

Here, each element uniquely determines a row, each of which contains all six elements in a unique order. That is to say, each element corresponds with a unique permutation of the set. If we were to write that out more concretely using our approach from the previous post, our permutations would look something like this:

val twoMod6 = Perm(
  0 -> 2,
  1 -> 3,
  2 -> 4,
  3 -> 5,
  4 -> 0,
  5 -> 1
)

This is no coincidence. Notice that we partially apply an element to get each row via this anonymous function: (m |+| _). Since each element has an inverse, this function can be inverted: (_ |-| m). So this function is actually a bijective function from a set of elements to itself, which, as we learned in the previous post, is a permutation by definition.

This holds for any group. Its elements correspond to a set of permutations because of the inverse. Furthermore, those permutations have a combining operation that gives them the same group structure (ie., its combination table looks identical). In more formal terms, every group is isomorphic to some permutation group. This fact is known as Cayley’s Theorem.

This is useful because permutations are often simpler to work with in calculations than a naive implementation of a group that they’re isomorphic to. If we have a group, we can implement its data types and operations in terms of permutations. Furthermore, every finite permutation group can be decomposed into a unique product of finite simple groups. These simple groups and their properties are well understood and can help reveal the structure of groups in the problem domain.

Example: Permutations of Three Elements

Let’s look at another concrete example of Cayley’s Theorem. Imagine you have a tile in the shape of an equilateral triangle. Consider the ways you can flip and rotate this tile so that it fits into its original outline. These different orientations of the tile are called the symmetries of a triangle.

These transformations form a group where the combining operation is sequential application of of transformations. For example, you can rotate the triangle clockwise, then flip it 180 degrees across its vertical axis, or you can perform this action in a single flip that switches the top corner with the left. The first two transformations combine to give a third transformation. Note that this operation is not commutative; flipping vertically then rotating, isn’t the same as rotating first then flipping vertically.

All in all, there are six symmetries of a triangle, as shown in this image:

S3 Diagram

The three corners are labeled so we can reference any of these transformations by reading off the labels from the triangle.

ABC ACB

BCA BAC

CAB CBA

We’ve seen these six words before. These are precisely the six permutations of the string "ABC" that we worked with in our previous post. We can represent our group of symmetries using the permutations we’ve already defined. These permutations themselves form a group under function composition:

implicit object PermGroup extends Group[Perm] {
  def empty = Map(A -> A, B -> B, C -> C)

  def inverse(p: Perm) = p.map(_.swap)

  def combine(p: Perm, r: Perm) = Perm(p.compose(r))
}

Let’s use this group definition to create a combination table analogous to the one we made for Mod6:

val perms = List(abc, acb, bac, bca, cab, cba)

val permsTable = perms.map(m => perms.map(m |+| _))

Our permutations are represented by Map instances that have a large toString, so we’ll simplify our table by instead using the index of each permutation from the above list:

scala> permsTable.map(_.map(perms.indexOf).mkString(" ")) foreach println
0 1 2 3 4 5
1 0 4 5 2 3
2 3 0 1 5 4
3 2 5 4 0 1
4 5 1 0 3 2
5 4 3 2 1 0

We’ve taken two different groups, the integers under addition modulo six, and the symmetries of an equilateral triangle, and found a way to represent them using permutations. The combination table for either shows that each element can be combined with every other element to get any of the six elements. We’ll use this in future posts where we use permutations to translate Rubik’s cube state and algorithms.