Coding guild Events Scala8 september 2017

This blog will look at the Monoid and is the 3rd in a sequence of 5, as a result of our Coding Guild session on August 1st about functional programming concepts. In the session, TypeClasses, Semigroups, Monoids, Functors and Applicatives were covered. The Cats library has been used, but not extensively introduced.

This time it is about Monoids. It builds upon the concepts that were covered in the previous blog posts (about Typeclasses and Semigroups). So if you didn’t read them yet …

We are still using the marbles and money domain:

case class Money(euros: Int, cents: Int)

trait Data {
  val moneys = List(Money(10,40), Money(4,95), Money(8, 99))
  val marbles = List(10, 4, 5)
}

We are reusing the Money case class. For brevity’s sake, I left out the imports, but those can be checked in the Github repo. Let’s sum up a list of Money and marbles (Int):

object SummingExample extends NamePrintingApp with Data {
  import Implicits._

  def addAllMoneys(moneys: List[Money])(implicit semigroup: Semigroup[Money]): Money = {
    moneys.foldLeft(Money(0,0)) { case (sum, money) =>
      sum |+| money
    }
  }
  def addAllMarbles(marbles: List[Int])(implicit semigroup: Semigroup[Int]): Int = {
    marbles.foldLeft(0) { case (sum, marble) =>
      sum |+| marble
    }
  }
  val balance = addAllMoneys(moneys)
  val marbleSum = addAllMarbles(marbles)

  println(s"balance: $balance")
  println(s"my marbles: $marbleSum")
}

In the previous post about Semigroups we already saw how the |+| operator works. Please revisit if it is not immediately clear how it works.

And when we run the code, in console it shows:

---- SummingExample  ----
balance: Money(24,34)
my marbles: 19

But ouch, replication again. If we look closely at the code we see that the only difference between the two functions is the initial empty value for the foldLeft. Let’s refactor. Let’s define a fold with the empty value as a parameter:

object AbstractExample extends NamePrintingApp with Data {
  import Implicits._

  def fold[A: Semigroup](list: List[A], empty: A): A = {
    list.foldLeft(empty) { case (sum, elem) =>
      sum |+| elem
    }
  }
  val balance = fold(moneys, Money(0, 0))
  val marbleSum = fold(marbles, 0)

  println(s"balance: $balance")
  println(s"my marbles: $marbleSum")
}

Nice, same results:

---- AbstractExample  ----
balance: Money(24,34)
my marbles: 19

The new code means that for every call we need to have an implicit Semigroup available, plus we need to pass an empty value on every call. But it can even simpler, with a Monoid. A Monoid is a Semigroup with an empty definition. Or, more formally: A Semigroup is a typeclass that defines an associative binary operation, called combine and an identity element:

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

The identity element empty implies that all instances of the type T are invariant under the combination of identity element:

Monoid[T].combine(a: T, Monoid[T].empty) == a
Monoid[T].combine(Monoid[T].empty, a: T) == a

That’s exactly what we need!

object MonoidExample extends NamePrintingApp with Data {
  implicit val moneyMonoid = new Monoid[Money] {
    override def combine(x: Money, y: Money): Money =
      Money(x.euros + y.euros + ((x.cents + y.cents) / 100), (x.cents + y.cents) % 100)

    override def empty: Money = Money(0, 0)
  }
  def fold[A: Monoid](list: List[A]): A = {
    list.foldLeft(Monoid[A].empty) { case (sum, elem) =>
      sum |+| elem
    }
  }
  val balance = fold(moneys)
  val marbleSum = fold(marbles)

  println(s"balance: $balance")
  println(s"my marbles: $marbleSum")
}
---- MonoidExample  ----
balance: Money(24,34)
my marbles: 19

This looks a lot better, but it seems like we are writing a really generic function that could easily be part of the Cats library. And so it does offer a generic fold:

trait Foldable[F[_]] {
  def fold[A](fa: F[A])(implicit A: Monoid[A]): A =
    foldLeft(fa, A.empty) { (acc, a) =>
      A.combine(acc, a)
    }
}

With this function our code can be simplified even more. We need a Foldable for our container type, List in our case. Cats provides this, thus we can write:

object FoldExample extends NamePrintingApp with Data {
  implicit val moneyMonoid = new Monoid[Money] {
    override def combine(x: Money, y: Money): Money =
      Money(x.euros + y.euros + ((x.cents + y.cents) / 100), (x.cents + y.cents) % 100)

    override def empty: Money = Money(0, 0)
  }
  import cats.instances.list._
  import cats.instances.int._ // is also imported in the examples ...

  val balance = Foldable[List].fold(moneys)
  val marbleSum = Foldable[List].fold(marbles)


  println(s"balance: $balance")
  println(s"my marbles: $marbleSum")
}

With this we can conclude that the monoid adds something to the Semigroup. Once you know these concepts you’ll start to see many places where you can use the monoid to simplify your code.

To get more acquainted with the monoid you can implement the exercise (exercise 3) below. Try to get the tests passing with the concepts in this blog.

import cats.implicits._
import cats.{Monoid, Semigroup}

object Domain {
  type Product = String
  type Price = Double
  type Number = Int

  val Catalog: Map[Product, Price] = Map(
    "cola" -> 2.75,
    "wine" -> 4.00,
    "beer" -> 3.25
  )

  case class Order(items: Map[Product, Number] = Map()) {
    def add(item: (Product, Number)): Order = Order(this.items |+| Map(item))

    // Implement using Fold
    def total(implicit monoid: Monoid[Price]): Double = ???
  }

  case class Person(name: String)

  implicit val personSemigroup = new Semigroup[Person] {
    override def combine(x: Person, y: Person): Person = Person(x.name |+| y.name)
  }

  implicit val orderSemigroup = new Semigroup[Order] {
    override def combine(x: Order, y: Order): Order = Order(x.items |+| y.items)
  }

  case class Table(personOrders: Map[Person, Order] = Map()) {
    def addPerson(person: Person): Table = Table(personOrders |+| Map(person -> Order()))
    def order(personOrder: (Person, Order)): Table = 
         Table(personOrders |+| Map(personOrder))

    def total: Price = ???
    def combine(other: Table): Table = ???
  }
}

where it should comply to:

import cats.implicits._
import cats.{Monoid, Semigroup}

import org.scalatest.{FlatSpec, Matchers}

class Test extends FlatSpec with Matchers {
  import Domain._

  it should "sum the total of an empty order" in {
    Order().total shouldBe 0
  }

  it should "sum the total of an order" in {
    Order(Map("cola" -> 1, "beer" -> 2, "wine" -> 3)).total shouldBe
      Catalog("cola") + Catalog("beer") * 2 + Catalog("wine") * 3
  }

  it should "be able to represent the bill for the combination of tables" in {
    val table1 = Table().order(Person("Michael") -> Order(Map("cola" -> 1, "wine" -> 1)))
                        .order(Person("John")    -> Order(Map("cola" -> 1, "beer" -> 2)))

    val table2 = Table().order(Person("Sophie")  -> Order(Map("wine" -> 1)))
                        .order(Person("Vanessa") -> Order(Map("beer" -> 1)))

    table1.combine(table2) shouldBe
      Table(
        Map(
          Person("Michael") -> Order(Map("cola" -> 1, "wine" -> 1)),
          Person("John")    -> Order(Map("cola" -> 1, "beer" -> 2)),
          Person("Sophie")  -> Order(Map("wine" -> 1)),
          Person("Vanessa") -> Order(Map("beer" -> 1))
        )
      )

    table1.combine(table2).total shouldBe 23.25
  }
}

All the code, including solutions of the exercises, are available on Github.