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.