Coding guild Events Scala21 augustus 2017

August 1st, we had another Coding Guild session, about functional programming concepts. In one session, TypeClasses, Semigroups, Monoids, Functors and Applicatives were covered. The Cats library has been used, but not extensively introduced. Together with Merlijn and Jeroen, I prepared examples and exercises to clarify these subjects.

This is the second in a series of articles, this time about Semigroups. The first was about typeclasses. In its core, a semigroup is a simple structure (from Wikipedia):

A semigroup is an algebraic structure consisting of a set together with an associative binary operation.

The binary operation of a semigroup is most often denoted multiplicatively: x·y, or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y). Associativity is formally expressed as that (x·y)·z = x·(y·z) for all x, y and z in the semigroup.

In the Cats library, the binary operation is called combine().

Let’s introduce the domain. This time, it is about marbles and money:

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

trait Data {
  // money
  val balance: Money = Money(987, 85)
  val salary: Money = Money(834, 78)
  val balances: Map[String, Money] = Map(
    "John" -> Money(987, 85),
    "Sara" -> Money(1234, 98)
  )
  val salaries: Map[String, Money] = Map(
    "Sara" -> Money(200, 90),
    "Mo" -> Money(4987,43)
  )

  // and marbles
  val marbles: Map[String, Int] = Map(
    "John" -> 6,
    "Sara" -> 9
  )
  val won: Map[String, Int] = Map(
    "Sara" -> 2,
    "Mo" -> 5
  )
}

We want to be able to add Money and Maps[String, Money] as well as Marbles and Maps[String, Marbles]; adding up the Money in two Maps will enable us to easily calculate a new balance per person if we have a Map with a starting balance and a Map with the salaries per person:

object BalanceExample extends NamePrintingApp with Data {

  // Function to add 2 money objects to each other
  def add(money: Money, other: Money): Money =
    Money(money.euros + other.euros + ((money.cents + other.cents) / 100), 
            (money.cents + other.cents) % 100)

  // Due to type erasure we need 2 functions for the maps
  def addMoneyMap(balances: Map[String, Money], 
                  salaries: Map[String, Money]): Map[String, Money] = {
    balances.foldLeft(salaries){
      case (acc, (name, money)) =>
        acc + (name -> acc.get(name).map(add(_, money)).getOrElse(money))
    }
  }
  def addMarbleMap(balances: Map[String, Int], 
                   marbles: Map[String, Int]): Map[String, Int] = {
    balances.foldLeft(marbles){
      case (acc, (name, nrOfMarbles)) =>
        acc + (name -> acc.get(name).map(_ + nrOfMarbles).getOrElse(nrOfMarbles))
    }
  }

  println(s"1. Add 2 money objects ${add(balance, salary)}")
  println(s"1. Payday adding Maps${addMoneyMap(balances, salaries)}")
  println(s"1. Game of marbles ${addMarbleMap(marbles, won)}")
}

When we run the code, the console displays:

---- BalanceExample  ----
1. Add 2 money objects: Money(1822,63)
1. Payday adding Maps: Map(Sara -> Money(1435,88), 
                           Mo -> Money(4987,43), 
                           John -> Money(987,85))
1. Game of marbles: Map(Sara -> 11, Mo -> 5, John -> 6)

So far, so good. But: adding the values of a Map for the same keys seems to be generic. Let’s abstract that away 😉 We create a typeclass Addable and define how to “add” two Maps of Addables:

object GenericAddBalanceExample extends NamePrintingApp with Data  {

  def add(money: Money, other: Money): Money =
    Money(money.euros + other.euros + ((money.cents + other.cents) / 100), 
          (money.cents + other.cents) % 100)

  trait Addable[T] {
    def add(a: T, b: T): T
  }
  // now we can use the same name, because type erasure is no longer playing parts
  // and curry in the addables to add two maps to each other
  def add[X, Y](balances: Map[X, Y], addMap: Map[X, Y])
               (addable: Addable[Y]): Map[X, Y] = {
    addMap.foldLeft(balances){
      case (acc, (name, plus)) =>
        acc + (name -> acc.get(name).map(addable.add(_, plus)).getOrElse(plus))
    }
  }

  println(s"2. Add 2 money objects: ${add(balance, salary)}")
  // With explicit Addable for money
  println(s"2. Payday adding Maps: ${add(balances, salaries)
                             {(a: Money, b: Money) => add(a,b)}}")
  // With explicit Addable for Int
  println(s"2. Game of marbles: ${add(marbles, won){(a: Int, b: Int) => a + b}}")
}

And again, the same results appear when we run the code:

---- GenericAddBalanceExample  ----
2. Add 2 money objects: Money(1822,63)
2. Payday adding Maps: Map(John -> Money(987,85), 
                           Sara -> Money(1435,88), 
                           Mo -> Money(4987,43))
2. Game of marbles: Map(John -> 6, Sara -> 11, Mo -> 5)

As mentioned, the addables are explicit; Scala enables us to make these implicit to even make the syntax even more concise:

object ImplicitsGenericAddBalanceExample extends NamePrintingApp with Data  {
  trait Addable[T] {
    def add(a: T, b: T): T
  }
  implicit val intAddable = new Addable[Int] {
    override def add(a: Int, b: Int): Int = a + b
  }
  // BONUS: Nice 2.12 trick for implementing single method interface
  implicit val moneyAddable: Addable[Money] = { (money, other) =>
      Money(money.euros + other.euros + ((money.cents + other.cents) / 100), 
            (money.cents + other.cents) % 100)
  }
  implicit def mapAddable[K, V: Addable] = new Addable[Map[K,V]] {
    override def add(a: Map[K, V], b: Map[K, V]): Map[K, V] =
      a.foldLeft(b){
        case (acc, (key, value)) =>
          acc + (key -> acc.get(key).map(implicitly[Addable[V]].add(_, value))
             .getOrElse(value))
      }
  }
  /**
    * Generic add function which can add anything as long as an Addable of it
    * is in implicit scope (or explicitly passed)
    */
  def add[A: Addable](a: A, b: A): A = implicitly[Addable[A]].add(a, b)

  println(s"3. Add 2 money objects: ${add(balance, salary)}")
  println(s"3. Payday adding Maps: ${add(balances, salaries)}")
  println(s"3. Game of marbles: ${add(marbles, won)}")
}

Running the code, it is getting boring, results in:

---- ImplicitsGenericAddBalanceExample  ----
3. Add 2 money objects: Money(1822,63)
3. Payday adding Maps: Map(Sara -> Money(1435,88), 
                           Mo -> Money(4987,43), 
                           John -> Money(987,85))
3. Game of marbles: Map(Sara -> 11, Mo -> 5, John -> 6)

So far we used straightforward Scala constructs. We defined a typeclass Addable, created instance of the Addable typeclass for adding Money and Int, and defined on a generic level how Map with Addable values can be aggregated.

In Functional Programming, we can also use Semigroups. A Semigroup is a typeclass that defines an associative binary operation, called combine.

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

The associative rule implies that combine(a, combine(b, c)) equals combine(combine(a, b), c). Addition and multiplication of numbers, and concatenation of strings, are associative operations. Subtraction is a counter example: (10 – 5) – 2 = 3 is not equal to 10 – (5 – 2) = 7.

The Cats library supplies a Semigroup typeclass and implementations of combining some primitive types such as Int (adding up) and Strings (concatenating). But it goes well beyond simple types: it also offers the ability to combine collections like Lists of semigroups (concatenating the lists) and Maps of semigroups (combining the value with the same key). Well, how convenient.

object CatsGenericAddBalanceExample extends NamePrintingApp with Data  {
  import cats.Semigroup
  // Let's define a Semigroup to combine (add) 2 money objects
  implicit val moneySemigroup = new Semigroup[Money] {
    override def combine(x: Money, y: Money): Money =
      Money(x.euros + y.euros + ((x.cents + y.cents) / 100), 
             (x.cents + y.cents) % 100)
  }
  // we get Int and Map for free, as mentioned before
  import cats.instances.int._
  import cats.instances.map._

  // before: def add[A: Addable](a: A, b: A): A = implicitly[Addable[A]].add(a, b)
  def add[A: Semigroup](a: A, b: A): A = implicitly[Semigroup[A]].combine(a, b)

  println(s"4. Add 2 money objects: ${add(balance, salary)}")
  println(s"4. Payday adding Maps: ${add(balances, salaries)}")
  println(s"4. Game of marbles: ${add(marbles, won)}")
}

And guess what will be printed when running this code:

---- CatsGenericAddBalanceExample  ----
4. Add 2 money objects: Money(1822,63)
4. Payday adding Maps: Map(Sara -> Money(1435,88), 
                           Mo -> Money(4987,43), 
                           John -> Money(987,85))
4. Game of marbles: Map(Sara -> 11, Mo -> 5, John -> 6)

By importing import cats.syntax.semigroup._ it is also possible to use |+| as a combine symbol.

  import cats.syntax.semigroup._

  println(s"5. Add 2 money objects ${balance.combine(salary)}")
  println(s"5. Payday adding Maps${balances |+| salaries}")
  println(s"5. Game of marbles ${marbles |+| won}")

No, I am not going to reveal what on the console now, take a guess.

For semigroups, there is an exercise as well (exercise1). Let’s get a drink:

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
  )
  object Order {
    import cats.Semigroup
    import cats.implicits._

    implicit val orderSemigroup = new Semigroup[Order] {
      override def combine(x: Order, y: Order): Order = Order(x.items |+| y.items)
    }
    // Combine using the semigroup
    def combineOrder(o1: Order, o2: Order): Order = ???

    // Implement using recursion
    def times(o1: Order, times: Int): Order = ???

    def combineN(o1: Order, times: Int): Order = ???
  }
  case class Order(items: Map[Product, Number])
}

The assignments are part of the model. It is accompanied with a test:

import org.scalatest.{FlatSpec, Matchers}

class Test extends FlatSpec with Matchers {
  import Domain._

  it should "Add orders correctly" in {
    val order1 = Order(Map("cola" -> 1, "wine" -> 2))
    val order2 = Order(Map("wine" -> 3, "beer" -> 5))

    Order.combineOrder(order1, order2) shouldBe 
       Order(Map("cola" -> 1, "wine" -> 5, "beer" -> 5))
  }

  it should "Add one order x number of times recursively" in {
    val order1 = Order(Map("wine" -> 1, "beer" -> 2))

    Order.times(order1, 5) shouldBe Order(Map("wine" -> 5, "beer" -> 10))
  }

  it should "Add 1 order x times using the semigroup's buildin functionality" in {
    val order1 = Order(Map("wine" -> 1, "beer" -> 2))

    Order.combineN(order1, 5) shouldBe Order(Map("wine" -> 5, "beer" -> 10))
  }
}

All the code and all answers to the exercises are available on Github.