# Adventures in Abstract Algebra Part I: Implementing Algebraic Structures in Scala

27 Aug 2015As programmers, we are often on the lookout for structure. If two distinct programs share the same structure, there are probably a variety of properties they also share. This can help us to begin reasoning about them even before we’ve grasped all the details. Ascending the ladder of abstraction allows us to focus on principles that can be applied to a wide range of cases. It also makes it possible to identify the form of a solution to novel problems.

Abstract algebra is the study of an interesting class of structures. We have an algebraic structure whenever we have a set and at least one binary operation on that set (satisfying a few simple properties). In this series, we’re going to try implementing some algebraic structures and think about how we might verify that an implementation satisfies a set of properties. We’ll also look briefly at how proving a piece of code instantiates an algebraic structure can enable us to draw conclusions about how the code will behave.

In this post, we’ll go over the basics of abstract algebra, identifying different algebraic structures by the algebraic properties they satisfy. We’ll then try our hand at implementing these structures in Scala.

In the second post in this series, we’ll turn our attention to finite algebraic structures and develop a method for proving that a given Scala implementation really satisfies the properties it’s supposed to.

In the third post, we’ll look at cases where this verification method breaks down because our target structure is too large to exhaustively test. We’ll use ScalaCheck to construct inductive (as opposed to deductive) arguments that an implementation of an infinite or large structure satisfies the relevant properties.

### Defining Algebraic Structures

Let’s begin with a brief overview of algebraic structures and their properties.

An **algebraic structure** consists of a set and a binary operation on ,
and is written <>. The binary operation must be
some total function that is closed over .

is a total function iff (if and only if) it is defined for any .

is closed over iff for any , .

As an example, consider addition over the positive integers. First, notice that we can add any two positive integers together. Second, notice that no matter which integers we choose, their sum is another positive integer. This means addition over the positive integers satisfies both totality and closure, respectively.

Addition, of course, is conventionally represented by , but it could just as easily be represented by . We will stick to the conventional symbols when appropriate, but continue to use when formulating general properties of binary operations.

Does division over the positive integers form an algebraic structure? It turns out that it does not. First, it is false that division is defined for any two positive integers (think of division by zero). Second, it is false that the quotient of any two positive integers is another positive integer. Consider . So division over the positive integers fails to satisfy either totality or closure, and thus fails to form an algebraic structure.

Mathematicians are interested in a variety of algebraic properties that can be used to distinguish algebraic structures and prove theorems about them. The properties we’ll be focusing on should be familiar from grade school arithmetic.

The first property we’ll look at is **associativity**:

*Associativity*: A binary operation is associative iff for any , .

An algebraic structure with an associative operation is called a **semi-group**.
Addition over the positive integers forms a semi-group, for example. For any
three positive integers , , and ,

Next, an algebraic structure can have an **identity element**:

*Identity Element*: An identity element exists for <> iff for any , .

A semi-group with an identity element is called a **monoid**. You’ll notice
that addition over positive integers does not form a monoid. That’s because
the identity element for addition is . But is not a positive
integer. However, addition over the natural numbers (defined as the
non-negative integers) does form a monoid. That’s because the non-negative
integers include zero, and so, for any natural number , we have
.

A monoid for which every element is **invertible** is called a **group**.
But what does it mean for an element to be invertible? It means that there
exists an inverse of , normally written .

*Inverse Element*: An inverse element exists for an iff there exists some element such that .

Notice that the existence of an inverse element depends on the existence of an
identity element . This means that any invertible algebraic structure
must also contain an identity element. A *group* is invertible, contains an
identity element, and has an associative binary operation.

Unfortunately, addition over the natural numbers fails to form a group, since it is false that every natural number has an inverse. has an inverse, namely itself. That’s because , and also happens to be the identity element for addition. But what is the inverse of ? There is no natural number that when added to yields .

Addition over the integers (negative and non-negative) does form a group, however. As we have already seen, is its own inverse. For any other integer , we can find an inverse by taking . This illustrates an important point. If an algebraic structure is invertible, there should exist a function mapping each element to its inverse. In the case of addition over the integers, that function is

Since , this function covers every integer.

Another example of a group is multiplication over the rational numbers without zero. The rational numbers, you’ll recall, are any numbers that can be put in the form . We find the inverse of a rational number (other than zero) by . It is always the case that . And of course is the identity element for multiplication.

We will go one step further and consider **commutativity**:

*Commutativity*: A binary operation is commutative iff for any , .

A group with a commutative operation forms an **abelian** or **commutative
group**. Addition over the integers once again fits the bill. That’s because
it doesn’t matter what order you add two integers. You’ll always get the
same result. The same holds for multiplication over the rational numbers
without zero.

Here’s a table of structures and their corresponding properties:

Associativity | Identity Element | Invertible | Commutativity | |
---|---|---|---|---|

Semi-Group | X | |||

Monoid | X | X | ||

Group | X | X | X | |

Abelian Group | X | X | X | X |

We’ve considered four kinds of algebraic structures, but we haven’t yet looked at any code. In the next section, we’ll look at one way to represent these algebraic structures in Scala.

### Scala Implementation

Let’s begin with the simplest possible algebraic structure. As you’ll recall, all we need is a set (possibly infinite) and a binary operation that is total and closed over .

```
trait AlgStruct[A] {
def op(a: A, b: A): A
def is(a: A, b: A): Boolean = (a == b)
}
```

Our binary operation is represented by `op`

, which has the signature
`(A, A) => A`

. We also add a method `is`

for checking equality
between members of our set. We can override this method if we need to define
equality or leave it be otherwise.

We are using a polymorphic type variable `A`

to represent the set .
Our operation takes two `A`

s and returns an `A`

. Is this enough
to satisfy totality and closure?

Closure appears to hold since `op`

returns an `A`

wherever it is
defined. But totality is not as clear cut. For example, consider a division
function with the signature `(Double, Double) => Double`

. This function
is not actually defined for every `Double`

. Think of division
by zero.

So although our trait `AlgStruct`

“claims” to represent the simplest
possible algebraic structure, our code does not ensure it. We will see this
pattern repeated in what follows. It’s only in Part II
of this series that we will
begin to address the question of how we can verify that a given implementation
of `AlgStruct`

really forms an algebraic structure.

We can provide an implementation by extending this trait. For example, if we want to represent addition over integers, we could write the following:

```
case class IntAdd extends AlgStruct[Int] {
def op(a: Int, b: Int): Int = a + b
}
```

Our set is all the Ints and our operation is addition. Now, Scala Ints are not identical to integers. For one thing, the integers are infinite and Ints are bounded. So for now we’ll stick with addition over Ints and hope it shares the relevant properties with addition over integers. We’ll address how to verify (or disprove) this guess in a later part of this series.

How do we represent our next algebraic structure, the *semi-group*? Recall
that a semi-group is an algebraic structure with an associative operation.
Here’s one approach:

```
trait SemiGroup[A] extends AlgStruct[A] {
//Op is associative
}
```

Not very impressive, perhaps. After all, this is just an `AlgStruct`

with a comment
thrown in. But since we’ve not yet determined how we’re going to check
algebraic properties, we’ll have to be satisfied with it for now. At the
moment, our contract with anyone implementing this trait is something like,
“Hey programmer, make sure your operation is associative.” We’ve not yet done
anything to help verify this.

The *monoid* (a semi-group with an identity element ) adds a little more
structure:

```
trait Monoid[A] extends SemiGroup[A] {
//Identity element
val e: A
}
```

Again, we’re counting on the person implementing this structure to supply
some `e`

that really does count as an identity element. Here’s an
example, sticking to addition over Ints.

```
case class IntAdd extends Monoid[Int] {
def op(a: Int, b: Int): Int = a + b
val e = 0
}
```

The last structure we’ll implement is the *group*, which we’ve already seen is
an invertible monoid. We’ll need to require an inverse function that maps every
in to its inverse element.

```
trait Group[A] extends Monoid[A] {
def inv(a: A): A
}
```

Addition over integers, as we’ve seen already, forms a group. We simply take the negative of any element to get its inverse. Perhaps this will work for addition over Ints as well, so we can write the following code:

```
case class IntAdd extends Group[Int] {
def op(a: Int, b: Int): Int = a + b
val e = 0
def inv(a: Int): Int = 0 - a
}
```

Though we’re not yet validating the fact that `inv`

really generates
inverse elements, it seems intuitively that adding any to
will yield . We’ll have to wait to see if we can verify this intuition for
Scala Ints.

We could continue with *abelian groups*, *rings*, *integral domains*, and
*fields*, but we’ll stop here. If you’re curious, you can see implementations
of these further structures in my GitHub project algebraic structures in Scala.

So far, we’ve provided the skeletons for several algebraic structures. However,
we’ve not yet proven that putative implementations satisfy the relevant
algebraic properties. We’re going to turn to this issue in Part II,
where we’ll
consider *finite structures* and employ a method I’ll be calling *exhaustion* to prove
that an implementation really is the structure it claims to be. We’ll then turn
to verifying implementations of infinite structures in Part III.