Generics, semigroup laws, and lying about code

September 08, 2015

What does the following code do?

def multiply(x: Int, y: Int): Int = // ...
multiply(6, 7)

If you guessed that it multiplies six by seven, you're wrong:

def multiply(x: Int, y: Int): Int = 42

It returns 42 no matter what arguments we pass:

multiply( 6,  7) // 42
multiply( 2,  3) // 42
multiply(-1, -1) // 42

It seems the developer who wrote this function has different expectations than we do.

We want multiply to return the product of its arguments for any possible arguments. We'll ignore integer wrap-around for simplicity.

How can we ensure that multiply does what we want?

We can use property-based testing to throw lots of random values at it and check the outcome:

val propMultiplyInt2 =
  forAll { (x: Int, y: Int) =>
    multiply(x, y) == x * y
  }
scala> propMultiplyInt2.check
! Falsified after 0 passed tests.
> ARG_0: 0
> ARG_1: 0
> ARG_1_ORIGINAL: 2038343578

This approach is fine, but we have to reimplement multiply as part of our test. Not only is this tautological, but it doesn't scale as the quantity and complexity of tests increases.

The (curried) type of multiply is Int => Int => Int. This looks familiar:

A semigroup is a set S together with a binary operation "" (that is, a function ⋅ : S × S → S) that satisfies the associative property:

For all a,b,c ∈ S, the equation (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c) holds.

Let's write a Semigroup instance for binary integer multiplication:

implicit val multiplyInt2: Semigroup[Int] =
  new Semigroup[Int] {
    def append(x: Int, y: => Int): Int = 42
  }

Let's also abstract multiply to use it:

def multiply[A : Semigroup](x: A, y: A): A =
  implicitly[Semigroup[A]].append(x, y)

Now we can use the Semigroup laws to validate it:

scala> semigroup.laws[Int].check
+ semigroup.semigroup.associative: OK, passed 100 tests.
! semigroup.left identity: Falsified after 0 passed tests.
> ARG_0: 1890298631
! semigroup.right identity: Falsified after 0 passed tests.
> ARG_0: 1

Our multiplication semigroup breaks both the left identity law and the right identity law. Let's fix it up:

implicit val multiplyInt2: Semigroup[Int] =
  new Semigroup[Int] {
    def zero: Int = 1
    def append(x: Int, y: => Int): Int = x * y
  }

Let's test it again:

scala> semigroup.laws[Int].check
+ semigroup.semigroup.associative: OK, passed 100 tests.
+ semigroup.left identity: OK, passed 100 tests.
+ semigroup.right identity: OK, passed 100 tests.

Much better.