A monoid is a semigroup with an identity element. Formally, the identity element z is an element for which an equation, z + x = x + z = x, holds for any x. This equation is called identity property. Both closure and associativity properties that are defined for semigroups are also required to hold for a monoid.

The existence of the identity property requires us to implement the monoid, as follows:

trait Monoid[S] extends Semigroup[S] {
  def identity: S
}

The check we specified for the semigroup also needs to be augmented for the monoid to verify that the new property holds:

def identity[S : Monoid : Arbitrary]: Prop =
  forAll((a: S) => {
    val m = implicitly[Monoid[S]]
    m.op(a, m.identity) == a && m.op(m.identity, a) == a
  })

def monoidProp[S : Monoid : Arbitrary]: Prop = associativity[S] && identity[S]

Now, we can define our first monoid, which will put all of the fish from the two buckets into a single bucket:

type Bucket[S] = List[S]

implicit val mergeBuckets: Monoid[Bucket[Fish]] = new Monoid[Bucket[Fish]] {
  override def identity: Bucket[Fish] = List.empty[Fish]
  override def op(l: Bucket[Fish], r: Bucket[Fish]): Bucket[Fish] = l ++ r
}

Here, we represent a Bucket with a List and just merge two buckets to denote that the contents of both have been put together. Are you curious to check if this implementation is a monoid? The property definition is unspectacular as it just delegates to the monoidProp we defined before:

implicit val arbBucketOfFish: Arbitrary[Bucket[Fish]] = Arbitrary(Gen.listOf(fishGen))

property("bucket of fish monoid") = {
  import Monoid.mergeBuckets
  monoidProp[Bucket[Fish]]
}

But, there is a bit of machinery underneath. First, we need to define a generator for buckets of fish so that we can use it to formulate a combined property of associativity and identity. Luckily, the property holds:

scala> implicit val arbBucketOfFish: Arbitrary[Bucket[Fish]] = Arbitrary(Gen.listOf(fishGen))
arbBucketOfFish: org.scalacheck.Arbitrary[Monoid.Bucket[Fish]] = org.scalacheck.ArbitraryLowPriority$$anon$1@3dd73a3d
scala> monoidProp[Bucket[Fish]]
res13: org.scalacheck.Prop = Prop
scala> .check
+ OK, passed 100 tests.

Are monoids only defined for containers? No, they're definitely not. Containers are just a special, comfortable case, because, in the majority of cases, it is obvious what should be an identity element of the corresponding monoid.

Looking away from containers and back to the colors example from the previous section, we can also pick an identity element for the operations we defined there to extend semigroups to monoids:

• Combining transparency would require a fully transparent identity element
• Combining shapes has an identity without a shape—a dot
• Combining colors might have a white color as an identity (this identity element will make the color less saturated, but it won't change the color itself)

We could even be creative and specify an identity element that's suitable for all of these operations—a fully transparent white-colored dot.

How about the other semigroups we've defined so far? From math, we know that natural numbers have identity elements for addition and multiplication, that is, zero and one, respectively. This allows us to upgrade the semigroups we implemented for ints to monoids:

implicit val intAddition: Monoid[Int] = new Monoid[Int] {
  override def identity: Int = 0
  override def op(l: Int, r: Int): Int = l + r
}

implicit val intMultiplication: Monoid[Int] = new Monoid[Int] {
  override def identity: Int = 1
  override def op(l: Int, r: Int): Int = l * r
}

This definition is similar to the one we had for the semigroup—we've just added the identity element to it. The implementation of the property check is also identical to what we had before.

Obviously, strings also form a monoid under concatenation and, as we noticed before, the identity element would be an empty container—a blank String:

implicit val stringConcatenation: Monoid[String] = new Monoid[String] {
  override def identity: String = ""
  override def op(l: String, r: String): String = l + r
}

Another nice thing about containers is that it is actually possible to not only define an algebraic structure in terms of the container as a whole, but to the reuse existing algebraic structures that have been defined for its elements.

This is the real power of abstract algebraic structures—they compose!

To demonstrate this, let's cheat a bit and define a weightless and toothless non-poisonousness fish with zero volume as an identity element for our fishing examples. Here is a definition for the big fish eats little fish monoid:

val ZeroFish = Fish(0,0,0,0)

implicit val weightMonoid: Monoid[Fish] = new Monoid[Fish] {
  override def identity: Fish = ZeroFish
  override def op(l: Fish, r: Fish): Fish =
    if (l.weight > r.weight) l.eat(r) else r.eat(l)
}

The monoids for the other three cases are implemented similarly by adding a ZeroFish as an identity element to all of them. 

Having this definition in scope, we can now implement the survival logic for two buckets of fish. First, we'll form a pair of fish from both buckets, and then one fish from the pair should survive:

implicit def surviveInTheBucket(implicit m: Monoid[Fish]): Monoid[Bucket[Fish]] =
  new Monoid[Bucket[Fish]] {
    override def identity: Bucket[Fish] = List.fill(100)(ZeroFish)
    override def op(l: Bucket[Fish], r: Bucket[Fish]): Bucket[Fish] = {
      val operation = (m.op _).tupled
      l zip r map operation
    }
  }

Here, we define our monoid in terms of a simpler monoid. The operation itself is built from the original operation converted to the tuple form and is applied to the pairs of fish from both buckets. This is defined for buckets of size less or equal than 100 because the identity bucket for this operation needs to contain enough ZeroFish in the case that the buckets we're combining have a different number of elements.

Now, we can test out different survival strategies just by having an instance of the desired monoid in scope:

property("props for survival in the bucket for most poisonousness") = {
  import Monoid.poisonMonoid
  import Monoid.surviveInTheBucket
  monoidProps[Bucket[Fish]]
}

We need to import both monoids in scope so that the implicit resolution works properly. In this example, from every pair of fish, the more toxic fish will survive. This can easily be changed by bringing a different monoid into scope, for example, the weightMonoid gives heavier fish a chance of survival:

scala> {
     | import ch07.Monoid.weightMonoid
     | import ch07.Monoid.surviveInTheBucket
     | monoidProp[Bucket[Fish]]
     | }
res3: org.scalacheck.Prop = Prop

scala> .check
+ OK, passed 100 tests.

We can check and see that the properties of the derived monoid hold. This can even be proved mathematically—by zipping two monoids, we created a product monoid, which has been proven to obey monoid laws.

Another interesting aspect of monoids and semigroups is their ability to be used to reduce any iterable collection to a single value.

For instance, the following is the reduce method that was defined for IterableOnce from the standard library:

def reduce[B >: A](op: (B, B) => B): B

This takes an associative binary operator and applies it between all elements of the collection. The type signature tells us that it is a good application for a semigroup as its operation satisfies the requirements of this function:

scala> val bucketOfFishGen: Gen[List[Fish]] = Gen.listOf(fishGen)
bucketOfFishGen: org.scalacheck.Gen[List[Fish]] = org.scalacheck.Gen$$anon$1@34d69633

scala> val bucket = bucketOfFishGen.sample.get
bucket: List[Fish] = List(Fish(98,44,11,22), Fish(69,15,57,18), ...

scala> bucket.reduce(poisonSemigroup.op)
res7: Fish = Fish(25,6,29,99)

In the preceding snippet, we generated a random bucket of fish and then applied the poisonSemigroup to it by specifying its operation as an argument for the reduce method.

Obviously, any semigroup operation is a perfect fit as soon as types match.

Unfortunately, the implementation of reduce throws an UnsupportedOperationException for empty collections, which makes it unsuitable for real functional programming:

scala> List.empty[Fish].reduce(poisonSemigroup.op)
java.lang.UnsupportedOperationException: empty.reduceLeft
  at scala.collection.IterableOnceOps.reduceLeft(IterableOnce.scala:527)
  at scala.collection.IterableOnceOps.reduceLeft$(IterableOnce.scala:524)
  at scala.collection.AbstractIterable.reduceLeft(Iterable.scala:759)
  at scala.collection.IterableOnceOps.reduce(IterableOnce.scala:496)
  at scala.collection.IterableOnceOps.reduce$(IterableOnce.scala:496)
  at scala.collection.AbstractIterable.reduce(Iterable.scala:759)
  ... 40 elided

There is a sibling of reduce called reduceOption that returns None for empty collections instead of throwing an exception, but this makes the whole result type optional.

There are a couple of similar methods defined on IterableOnce. Grouping them together would allow us to represent the "reducibility" property as a standalone concept:

trait Reducible[A] {

  @throws("UnsupportedOperationException ")
  def reduceLeft(op: (A, A) => A): A

  @throws("UnsupportedOperationException ")
  def reduceRight(op: (A, A) => A): A

  @throws("UnsupportedOperationException ")
  def reduce(op: (A, A) => A): A = reduceLeft(op)

  def reduceLeftOption(op: (A, A) => A): Option[A]

  def reduceRightOption(op: (A, A) => A): Option[A]

  def reduceOption(op: (A, A) => A): Option[A] = reduceLeftOption(op)

}

This does not look very nice because, as we have already discussed, the methods either throw an exception or introduce an effect of optionality. How could we improve this implementation? We could make use of the monoids' identity property!