Semigroup is probably the simplest yet most useful algebraic structure. It is fully defined by two qualities:

• It is defined for some (possibly infinite) set of elements
• It has a binary operation defined for any pairs of elements in this set

It also has the following two properties:

• The operation is closed, which means that the result of the operation belongs to the same set as its operands
• The operation is associative, meaning that multiple operations should produce the same result, regardless of the order in which they are applied

We can translate these definitions into the Scala code almost literally:

trait Semigroup[S] {
 def op(l: S, r: S): S
}

S denotes the type that the set elements belong to, and op denotes the operation. The result type is also S—we have defined the property of closeness of the operation on the type level. Formally, it is said that S forms a semigroup under op.

Readers that are familiar with Chapter 5, Property-Based Testing in Scala, will also remember that we talked about associativity as one of the ways to formulate ScalaCheck properties. It is very easy to define this property to check the second semigroup law in the same way we mentioned earlier:

import org.scalacheck._
import org.scalacheck.Prop._
def associativity[S : Semigroup : Arbitrary]: Prop =
  forAll((a: S, b: S, c: S) => {
    val sg = implicitly[Semigroup[S]]
    sg.op(sg.op(a, b), c) == sg.op(a, sg.op(b, c))
  })

We need the S type to have a Semigroup and Arbitrary, the former of which we need to get the implementation we want to check and the latter to be able to generate random data for S.

The property itself, sg.op(sg.op(a, b), c) == sg.op(a, sg.op(b, c)), just verify that operations that are applied in a different order produce the same result—exactly as specified verbally.

Please note that properties we define in this chapter can also be executed by running tests in SBT directly. To do this, it is enough to start the SBT session and type test followed by the Enter key.

OK, we now have a definition of a semigroup for S and a way to check that the semigroup is properly implemented, but what are these S's? Well, this is the beauty of the abstract algebraic data structure. The S can be absolutely anything as long as semigroup laws hold. As an example, we can stick to our figure of speech regarding fishing.

We can specify at least two eat operations for S that are defined on all of the fish. The the big fish eats the little fish operation is defined on two fish with the result that the bigger fish has a volume equal to the sum of the volumes of both fish participating in the operation. Similarly, the heavy fish eats the light fish is defined by the same principle but in terms of the fish's weight. It's easy to see that the first property of this semigroup holds by definition. The following diagrams represent the proof for the second property. The first diagram illustrates the associativity of the Big eats small/Heavy eats light operation on the fish:

The following diagram illustrates the same property for the More teeth win rule:

Figure 2: More teeth win

This final illustration shows that associativity also holds for the property of toxicity: 

The semigroup operation does not need to be an addition. For instance, we can define it so that, from both participants, the most poisonous fish is on the left as a result. This book has no age restriction, so we should pretend that the second fish was scared away in the process. But experienced fishers know the creatures—instead, we have to constrain the semigroup for this operation to the set of all living fish, which allows us to avoid ambiguity for the result of the operation.

As per our analogy, we could define another operation in terms of teeth—the fish with the bigger teeth is on the left as a result of the operation. Again, to avoid ambiguity, our semigroup is formed by solid, living fish under this operation.

In order to implement the semigroups we just defined, we need a definition of fish. Let's have it represented as a case class:

final case class Fish(volume: Int, size: Int, teeth: Int, poisonousness: Int)

The relevant properties are represented as fields.

Let's start with the big and small fish semigroup. The law checking property we defined previously requires an implicit semigroup in scope, so we'll mark our instance as implicit:

implicit val volumeSemigroup: Semigroup[Fish] = (l: Fish, r: Fish) => {
  val result = if (l.volume >= r.volume) l else r
  result.copy(volume = r.volume + l.volume)
}

We can check which fish wins by comparing their volumes. The bigger fish incorporates the volume of the fish eaten during the operation.

At the moment, some of you must be scratching your heads, trying to remember why this structure looks so familiar. The astute reader will have already recognized the type class pattern we talked about in Chapter 4, Getting to Know Implicits and Type Classes. Good job, astute reader!

Our implementation is so simple that it cannot be incorrect, but for completeness' sake, let's define a property for it. First, we need a generator for Fish:

val fishGen: Gen[Fish] = for {
  weight <- Gen.posNum[Int]
  volume <- Gen.posNum[Int]
  poisonousness <- Gen.posNum[Int]
  teeth <- Gen.posNum[Int]
} yield Fish(volume, weight, teeth, poisonousness)

implicit val arbFish: Arbitrary[Fish] = Arbitrary(fishGen)

We implement it by combining generators for single properties, exactly as we did in Chapter 4, Getting to Know Implicits and Type Classes. Now, defining the check itself boils down to importing the proper implicit and delegating to the property we defined previously:

property("associativity for fish semigroup under 'big eats little'") = {
  associativity[Fish]
}

The definitions of the properties in this chapter cannot be pasted in REPL because they need to be placed in a test wrapper. Please see the accompanying code to see how it is done.

Running this property is also done in the same way as in Chapter 4, Getting to Know Implicits and Type Classes, so there should be no surprises here:

scala> associativity[Fish]
res1: org.scalacheck.Prop = Prop
scala> .check
! Falsified after 3 passed tests.
> ARG_0: Fish(2,3,2,1)
> ARG_1: Fish(2,3,3,3)
> ARG_2: Fish(3,2,3,2)

Ouch, it turns out there are surprises! Our implementation does not satisfy the associativity requirements for the case where the fish have the same volume!

This little case demonstrates how important it is to check that an implementation of an abstract algebraic structure obeys the laws defined for it for all possible input values. In our case, we don't actually have a proper semigroup implementation yet. Let's fix that by pretending that the bigger fish incorporates all of the properties of the eaten one. This might look strange for the number of teeth and venom, but we're talking about abstractions, after all:

final case class Fish(volume: Int, weight: Int, teeth: Int, poisonousness: Int) {
  def eat(f: Fish): Fish = Fish(volume + f.volume, weight + f.weight, teeth + f.teeth, poisonousness + f.poisonousness)
}

This gives us a slightly simpler semigroup implementation:

implicit val volumeSemigroup: Semigroup[Fish] = (l: Fish, r: Fish) =>
  if (l.volume > r.volume) l.eat(r) else r.eat(l)

In the case of the fish being of an equal volume, the right fish wins. This is a random choice, but this makes our semigroup right-biased.

Let's retry our check (if you're playing with the code in REPL, you'll need to paste the definition of fishGen and arbFish again to apply them to the new definition of the Fish):

scala> associativity[Fish]
res10: org.scalacheck.Prop = Prop
scala> .check
+ OK, passed 100 tests.

This states that we are on the right track—it passes.

We can define and check other semigroups by analogy:

implicit val weightSemigroup: Semigroup[Fish] = (l: Fish, r: Fish) =>
  if (l.weight > r.weight) l.eat(r) else r.eat(l)

implicit val poisonSemigroup: Semigroup[Fish] = (l: Fish, r: Fish) =>
 if (l.poisonousness > r.poisonousness) l else r

implicit val teethSemigroup: Semigroup[Fish] = (l: Fish, r: Fish) =>
 if (l.teeth > r.teeth) l else r

This code reflects our earlier discussion about how different attributes of the fish work during the operation. The definition is basically always the same; it just refers to the different properties of the fish! We omitted the definition of the ScalaCheck properties because they are identical to the ones we already looked at.

It would be a disappointment if semigroups were only useful in the realm of fishing. Let's take a look at another example—mixing colored shapes:

We can pick one of the following operations to work with:

• Combine transparency 
• Combine shapes
• Combine colors (represented as textures on the image)

These are represented in the following diagrams. The first addresses the transparency:

The second is about combining shapes in a consistent way:

Figure 5: Combining shapes

This final diagram shows us that combining colors (fillings) produces the same result as well:

Figure 6: Combining colors (fillings)

The preceding diagrams provide proof that the associative law holds and that the closure property again holds by definition.

Have you noticed the commonality between both the fishing and shapes examples? We pick a numeric property of the entity and apply an operation to this property. For instance, all of our fishing examples can be reduced to just two cases: integer addition (for volume and weight) and integer comparison (for teeth and poisonousness).

Of course, we also can specify semigroups for these cases. The numbers form a semigroup under addition as well as under multiplication. We can demonstrate this with an example of the Int type:

implicit val intAddition: Semigroup[Int] = (l: Int, r: Int) => l + r
implicit val intMultiplication: Semigroup[Int] = (l: Int, r: Int) => l * r

property("associativity for int under addition") = {
  import Semigroup.intAddition
  associativity[Int]
}
property("associativity for int under multiplication") = {
  import Semigroup.intMultiplication
  associativity[Int]
}

This definition is completely analogous to what we had before, and so is the result of the execution of the test command in SBT:

+ Semigroup.associativity for int under addition: OK, passed 100 tests.
+ Semigroup.associativity for int under multiplication: OK, passed 100 tests.

Strings form semigroups under concatenation:

implicit val stringConcatenation: Semigroup[String] = 
  (l: String, r: String) => l + r

property("associativity for strings under concatenation") = {
  import Semigroup.stringConcatenation
  associativity[String]
}

This semigroup is implemented entirely like the others, but conceptually this is a bit different from what we had before. In the case of a String, the operation is defined not in terms of some property but in terms of content. In a sense, we're defining a semigroup for the container of chars and the operation is specified as bringing the contents of both containers together in an ordered fashion.

In our fishing realm, a similar example would be a combination of two fish: one with caviar and one with milk, which would spawn a number of smaller fish as a result. This can't be an example of a semigroup as long as we're talking about single fish because the operation is not closed—we expect a single fish as a result, but the operation returns many of them. We can turn the situation around if we start to talk about buckets of fish. Combining two buckets, each with a single fish, will produce a bucket full of small fish. This operation is closed and if we can prove that it is associative, this would be a valid example of a semigroup.

Switching perspectives from a single item to a container has another subtle effect: it is now possible to have an empty container (bucket) for any operation. In the situation where one of the operands is an empty container, the operation just returns another operand as a result. This makes our abstraction more powerful. It turns a semigroup into a monoid.