# 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.