## Property Based Testing

### Functional programming in Scala

The following set of sections represent the exercises contained in the book "Functional Programming in Scala", written by Paul Chiusano and Rúnar Bjarnason and published by Manning. This content library is meant to be used in tandem with the book. We use the same numeration for the exercises for you to follow them.

Note: some of the exercises in this chapter are somewhat open-ended, and weren't included in this section. You can always head to the official repository containing hints for all exercises available in the book.

### A brief tour of property-based testing

Exercise 8.1

To get used to property testing, let's try to figure out the properties that specify the implementation of a `sum: List[Int] => Int` function:

``````* The sum of the empty list is 0.
* The sum of a list whose elements are all equal to `x` is just the list's length multiplied by `x`. We might
express this as `sum(List.fill(n)(x)) == n * x`
* For any list, `l`, `sum(l) == sum(l.reverse)`, since addition is commutative.
* Given a list, `List(x,y,z,p,q)`, `sum(List(x,y,z,p,q)) == sum(List(x,y)) + sum(List(z,p,q))`, since addition is
associative. More generally, we can partition a list into two subsequences whose sum is equal to the sum of the
overall list.
* The sum of 1,2,3...n is `n*(n+1)/2`.``````

Exercise 8.2

Likewise, these would be the properties that specify a function that finds the maximum of a `List[Int]`:

``````* The max of a single element list is equal to that element.
* The max of a list is greater than or equal to all elements of the list.
* The max of a list is an element of that list.
* The max of the empty list is unspecified and should throw an error or return `None`.``````

### The meaning and API of properties

Exercise 8.3

Taking this representation of `Prop`, let's implement `&&`:

``````trait Prop { def check: Boolean }

def &&(p: Prop): Prop = new Prop {
def check = Prop.this.check && p.check
}``````

Let's try it out while testing a couple of properties for Strings. First, a substring of a String containing its last character should be the same that accessing the character directly. Secondly, calling `startsWith` on a string should yield an affirmative result when compared to the original string.

``````val genString = Gen.stringN(5)

val propA = forAll(genString)(s => s.substring(res0) == s.charAt(res1).toString)
val propB = forAll(genString)(s => s.startsWith(s) == res2)

// Don't worry about the implementations of run and its types, we'll deal with it later:
val result = (propA && propB).run(100, 100, RNG.Simple(System.currentTimeMillis))
result shouldBe Passed``````

### The meaning and API of generators

Exercise 8.4

Let's implement `Gen.choose` using the following representation for `Gen`:

``case class Gen[A](sample: State[RNG, A])``

`choose` should generate integers in the range `start` to `stopExclusive`:

``````def choose(start: Int, stopExclusive: Int): Gen[Int] =
Gen(State(RNG.nonNegativeInt).map(n => start + n % (stopExclusive - start)))

val rng = RNG.Simple(47)
// We use sample on the Gen instance to generate a State containing a RNG and an Int value. We can then run it and
// obtain both the random-generated number and a new generator to keep generating more.
choose(res0, 10).sample.run(rng)._1 should be >= res1
choose(0, res2).sample.run(rng)._1 should be < res3``````

Exercise 8.5

We can implement other functions for `Gen`. Let's look at them, starting by `unit`, that always generates the same value:

``````def unit[A](a: => A): Gen[A] = Gen(State.unit(a))

val rng = RNG.Simple(47)
unit(42).sample.run(rng)._1 shouldBe res0
unit("foo").sample.run(rng)._1 shouldBe res1``````

`boolean` generates random `Boolean` values:

``val boolean: Gen[Boolean] = Gen(State(RNG.boolean))``

We can also implement `listOfN`, a function that generates lists of length `n` using the provided generator:

``````def listOfN[A](n: Int, g: Gen[A]): Gen[List[A]] =
Gen(State.sequence(List.fill(n)(g.sample)))

val rng = RNG.Simple(47)
val listOfBooleans = listOfN(10, Gen.boolean).sample.run(rng)._1
listOfBooleans.size shouldBe res0

listOfN(3, Gen.unit(42)).sample.run(rng)._1 shouldBe res1``````

### Generators that depend on generated values

Exercise 8.6

`flatMap`, lets one generator depend on another. This is its implementation:

``````def flatMap[B](f: A => Gen[B]): Gen[B] =
Gen(sample.flatMap(a => f(a).sample))``````

We can use `flatMap` to implement a more dynamic version of `listOfN`:

``````def listOfN_1[A](size: Gen[Int], g: Gen[A]): Gen[List[A]] =
size flatMap (n => Gen.listOfN(n, g))

val rng = RNG.Simple(47)
val intGen = choose(0, 10)
val generatedList = listOfN_1(intGen, unit(42)).sample.run(rng)._1
generatedList.size should be >= res0
generatedList.size should be < res1

listOfN_1(Gen.unit(1), Gen.unit(42)).sample.run(rng)._1 shouldBe res2``````

Exercise 8.7

Through the use of `flatMap` we can implement `union`, a function to combine two generators of the same type into one, by pulling values from each one with the same likelihood:

``````def union[A](g1: Gen[A], g2: Gen[A]): Gen[A] =
boolean.flatMap(b => if (b) g1 else g2)``````

Exercise 8.8

Following a similar principle we can implement `weighted`, a version of `union` accepting a weight for each `Gen` and generates values from each one with a probability proportional to its weight:

``````def weighted[A](g1: (Gen[A], Double), g2: (Gen[A], Double)): Gen[A] = {
// The probability we should pull from `g1`.
val g1Threshold = g1._2.abs / (g1._2.abs + g2._2.abs)
Gen(State(RNG.double).flatMap(d => if (d < g1Threshold) g1._1.sample else g2._1.sample))
}``````

Exercise 8.9

Let's implement `&&` and `||` to compose `Prop` values:

``````def &&(p: Prop) = Prop {
(max, n, rng) =>
run(max, n, rng) match {
case Passed | Proved => p.run(max, n, rng)
case x => x
}
}

def ||(p: Prop) = Prop {
(max, n, rng) =>
run(max, n, rng) match {
// In case of failure, run the other prop.
case Falsified(msg, _) => p.tag(msg).run(max, n, rng)
case x => x
}
}``````

Let's try those out:

``````val genZeroToTen = Gen.choose(0, 10)
val genElevenToTwenty = Gen.choose(11, 20)
val genCombination = Gen.union(genZeroToTen, genElevenToTwenty)

val combinedProp = (forAll(genCombination)(_ < 10) ||
forAll(genCombination)(_ < 20)) &&
forAll(genCombination)(_ >= 0)

val result = combinedProp.run(100, 100, RNG.Simple(System.currentTimeMillis))
result shouldBe res0``````

### Test case minimization

Exercise 8.10

Let's implement helper functions to convert `Gen` into the new `SGen` type:

``````case class SGen[+A](forSize: Int => Gen[A])

case class Gen[+A](sample: State[RNG, A]) {
// ...
def unsized: SGen[A] = SGen(_ => this)
}``````

Exercise 8.11

`SGen` supports many of the same operations as `Gen`. Let's define some convenience functions of `SGen` that just delegate to their counterparts on `Gen`:

``````case class SGen[+A](g: Int => Gen[A]) {
def apply(n: Int): Gen[A] = g(n)

def map[B](f: A => B): SGen[B] = SGen { g(_) map f }

def flatMap[B](f: A => SGen[B]): SGen[B] = {
val g2: Int => Gen[B] = n => {
g(n) flatMap { f(_).g(n) }
}
SGen(g2)
}

def **[B](s2: SGen[B]): SGen[(A, B)] =
SGen(n => apply(n) ** s2(n))
}``````

Exercise 8.12

We can also implement a `listOf` combinator that doesn't need an explicit size. It should return an `SGen`, and its implementation should generate lists of the requested size. Let's try it out:

``````def listOf[A](g: Gen[A]): SGen[List[A]] =
SGen(n => g.listOfN(n))

val gen = Gen.unit(42)
val prop = forAll(listOf(gen))(l => l.forall(_ == res0))
prop.run(100, 100, RNG.Simple(System.currentTimeMillis)) shouldBe Passed``````

### Using the library and improving its usability

Exercise 8.13

Let's define a `listOf1` function to generate nonempty lists:

``````def listOf1[A](g: Gen[A]): SGen[List[A]] =
SGen(n => g.listOfN(n max res0))

val prop = forAll(listOf1(Gen.choose(0, 10)))(l => l.size == 1 && l.forall(_ < 10))
prop.run(100, 100, RNG.Simple(System.currentTimeMillis))``````

Exercise 8.14

Now let's write a property to verify the behavior of `List.sorted`:

``````val sortedProp = forAll(listOf(smallInt)) { ns =>
val nss = ns.sorted
// We specify that every sorted list is either empty, has one element,
// or has no two consecutive elements `(a,b)` such that `a` is greater than `b`.
(nss.isEmpty || nss.tail.isEmpty || !nss.zip(nss.tail).exists {
case (a, b) => a > b
})
// Also, the sorted list should have all the elements of the input list,
&& ! ns.exists(!nss.contains(_))
// and it should have no elements not in the input list.
&& ! nss.exists(!ns.contains(_))
}``````

### Writing a test suite for parallel computations

Exercise 8.16

We can write a generator for Par[Int], building deeply nested parallel computations. Take a look:

``````// A `Gen[Par[Int]]` generated from a list summation that spawns a new parallel
// computation for each element of the input list summed to produce the final
// result. This is not the most compelling example, but it provides at least some
// variation in structure to use for testing.

val pint2: Gen[Par[Int]] = choose(-100, 100).listOfN(choose(0, 20)).map(l =>
l.foldLeft(Par.unit(0))((p, i) =>
Par.fork { Par.map2(p, Par.unit(i))(_ + _) }))``````

Exercise 8.17

With `pint2` we can express the property about `fork` from chapter 7 (`fork(x) == x`):

``val forkProp = Prop.forAllPar(pint2)(i => equal(Par.fork(i), i)) tag "fork"``

#### Testing higher-order functions

Exercise 8.18

Let's show how we can test higher-order functions with `takeWhile` and `dropWhile` from `List`:

``````val prop = forAll(listOf(Gen.choose(0, 20))) { l =>
val index = Gen.choose(0, 20).sample.run(RNG.Simple(47))._1
l.takeWhile(_ < index) ++ l.dropWhile(_ < index) == l
}
prop.run(100, 100, RNG.Simple(System.currentTimeMillis)) shouldBe res0``````