Functional Design Patterns in Scala: Monoids

Monoids are used to describe an aggregation pattern: whenever we need to combine values of a particular type, a monoid instance helps abstract the mechanics of the aggregation from the program’s business logic. In this post, we will use the LCD Digits kata that we tackled previously as a motivating example for applying this pattern. The goal here is to transform a sequence of input digits into a string resembling their representation on an LCD display. For example, given the input 0123456789, the program should produce:

._. ... ._. ._. ... ._. ._. ._. ._. ._.
|.| ..| ._| ._| |_| |_. |_. ..| |_| |_|
|_| ..| |_. ._| ..| ._| |_| ..| |_| ..|

As before, we will use a case class to represent LCD digits as a product type:

case class LCDDigit(firstRow: String, secondRow: String, thirdRow: String)

We can then declare each digit 0-9 as an instance of this class in the associated companion object:

object LCDDigit {
  val zero = LCDDigit(
    "._.",
    "|.|",
    "|_|"
  )
  val one   = LCDDigit("...", "..|", "..|")
  val two   = LCDDigit("._.", "._|", "|_.")
  val three = LCDDigit("._.", "._|", "._|")
  val four  = LCDDigit("...", "|_|", "..|")
  val five  = LCDDigit("._.", "|_.", "._|")
  val six   = LCDDigit("._.", "|_.", "|_|")
  val seven = LCDDigit("._.", "..|", "..|")
  val eight = LCDDigit("._.", "|_|", "|_|")
  val nine  = LCDDigit("._.", "|_|", "..|")
}

Whereas in our previous solution we used higher-order functions to handle the aggregation of digits, in this version we will perform this aggregation with a monoid instance for the LCDDigit type. A monoid is a specialisation of a semigroup, an algebraic structure comprising a set and some associative operation combine, that also has some identity element id for which the following must be true: For all elements _s_ from set S, combine(s, id) == combine(id, s) == s. In practice, these properties enable us to merge elements from a (possibly empty) collection. For convenience, Monoid is provided as a type class in the cats library:

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

For our LCDDigit type, we construct an instance of Monoid, specifying in the combine function how two LCDDigit values should be merged, and providing a value for the identity element in the implementation of empty. We will place this monoid instance inside the LCDDigit companion object so that it gets added to the implicit scope whenever the LCDDigit type is imported.

import $ivy.`org.typelevel::cats:0.9.0`, cats.Monoid

implicit val ConcatMonoid = new Monoid[LCDDigit] {
  override def empty = LCDDigit("", "", "")
  override def combine(l1: LCDDigit, l2: LCDDigit): LCDDigit =
    LCDDigit(
      l1.firstRow  + " " + l2.firstRow,
      l1.secondRow + " " + l2.secondRow,
      l1.thirdRow  + " " + l2.thirdRow)
}

For the purposes of this example, we will omit the parsing of strings into sequences of LCDDigits since we can reuse the approach from our previous solution, but we will add some syntactic sugar for working with this type by declaring an implicit class within the companion object:

import $ivy.`org.typelevel::cats:0.9.0`, cats.Show

implicit val ShowInstance = Show.show[LCDDigit](_.productIterator mkString "\n")

implicit class Extensions(l1: LCDDigit) {
  def show = ShowInstance.show(l1)
  def merge(l2: LCDDigit) = ConcatMonoid.combine(l1, l2)
}

This allows us to format aggregations of LCDDigits as follows:

import LCDDigit._

val monoidInstance = implicitly[Monoid[LCDDigit]]

val fiveFourSix = Seq(five, four, six)
val digits = monoidInstance.combineAll(fiveFourSix)
println(digits.show)
  // ._. ... ._.
  // |_. |_| |_.
  // ._| ..| |_|

val noDigits = monoidInstance.combineAll(List())
println(noDigits.show)
  //
  //
  //

/* Because ConcatMonoid is also an instance of a semigroup, we
   can use the infix |+| operator for combining LCDDigit values */
import cats.implicits._

val ten = one |+| zero

println(ten.show)
  // ... ._.
  // ..| |.|
  // ..| |_|

The way in which LCDDigit elements should be combined is fairly obvious; however, suppose we are working with a different data type in which we are required to support mulitiple strategies for merging values. For example, consider possible aggregations for Company instances (each of which has a name and a market value):

case class Company(name: String, value: Int)

One such aggregation might be to form a new company by concatenating their names and summing their market values (simulating the possible effect of a merger); another might be to select the input company with the highest market value. We can define separate monoidal instances in the Company companion object to represent these two effects:

object Company {
  implicit val CompanyMergeMonoid = new Monoid[Company] {
    def empty = Company("", 0)
    def combine(t1: Company, t2: Company) =
      Company(t1.name + t2.name, t1.value + t2.value)
  }

  implicit val EliminateCompetitorsMonoid = new Monoid[Company] {
    def empty = Company("", 0)
    def combine(t1: Company, t2: Company) = Set(t1, t2) maxBy (_.value)
  }
}

Because there are now two implicit monoid instances in scope, we need to pass one explicitly when declaring an aggregation:

import Monoid._
import Company._

val c1 = Company("A", 10)
val c2 = Company("B", 20)
val c3 = Company("C", 30)
val c4 = Company("D", 40)

val cs = List(c1, c2, c3, c4)

val res1 = combineAll(cs)(CompanyMergeMonoid)
val res2 = combineAll(cs)(EliminateCompetitorsMonoid)

println(res1)
  // Company(ABCD,100)

println(res2)
  // Company(D,40)

The benefit of using a monoidal approach here is that the aggregations are encapsulated in the companion object of the domain entity; the business logic only needs to declare that a particular aggregation should be performed, without needing to specify exactly how this should happen. By contrast, this natural separation of concerns would not be achieved if we were to define the aggregation in-line, using a fold:

cs.foldLeft(Company("", 0))((a,b) => Company(a.name + b.name, a.value + b.value))

Monoids are therefore an important pattern for the functional scala developer, and should be considered whenever there is a need to combine values in some way or another.

If you are interested in experimenting further with the examples presented in this post, the snippets below can be used as worksheets in an IDE or with a tool like ammonite: LCDDigitsRedux CompanyExample