Functional Random Generators

In the last lecture, we saw that besides lists, sequences and even collections, you can use for on your own types as well – you must only define map, flatMap and withFilter for these types.

Here we will see an example.

Random Values

You know about random numbers:

import java.util.Random

val rand = new Random
rand.nextInt()

Question: What is a systematic way to get random values for other domains, such as:

booleans, strings, pairs and tuples, lists, sets, trees

Generators

Let’s define a trait Generator[T] that generates random values of type T:

trait Generator[+T] {
    def generate: T
}

Some instances:

// Random Integer
val integers = new Generator[Int] {
    val rand = new java.util.Random
    def generate = rand.nextInt()
}

// Random Boolean
val booleans = new Generator[Boolean] {
    def generate = integers.generate > 0
}

// Random Pairs
val pairs = new Generator[(Int, Int)] {
    def generate = (integers.generate, integers.generate)
}

Streamlining

Can we avoid the new Generator[...] boilerplate? Yes we can, using the for expression.

Ideally we want to write:

val booleans = for (x <- integers) yield x > 0 // integers is as defined above

def pairs[T, U](t: Generator[T], u: Generator[U]) = for {
    x <- t
    y <- u
} yield (x, y)

Here the for used in booleans expands to use a map and the for used in the pairs expands to use a flatMap. Hence we will need to implement map and flatMap for this:

trait Generator[+T] {
    self => // an alias for ”this”.
    def generate: T
    def map[S](f: T => S): Generator[S] = new Generator[S] {
        def generate = f(self.generate) // this.generate would have called the generate defined on this line itself. Hence we call self.generate to invoke the one defined on the line above
    }
    def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
        def generate = f(self.generate).generate
    }
}

More examples:

def single[T](x: T): Generator[T] = new Generator[T] {
    def generate = x
}

def choose(lo: Int, hi: Int): Generator[Int] = {
    for (x <- integers) yield lo + x % (hi - lo)
}

def oneOf[T](xs: T*): Generator[T] = {
    for (idx <- choose(0, xs.length)) yield xs(idx)
}
// usage oneOf("Red","Green","Yellow")

List Generator: generates an empty list or a non-empty list.

def lists: Generator[List[Int]] = for {
    isEmpty <- booleans
    list <- if (isEmpty) emptyLists else nonEmptyLists
} yield list

def emptyLists = single(Nil)

def nonEmptyLists = for {
    head <- integers
    tail <- lists
} yield head :: tail

Application: Random Testing

You know about units tests:

• Come up with some some test inputs to program functions and a postcondition.
• The postcondition is a property of the expected result.
• Verify that the program satisfies the postcondition.

Question: Can we do without the test inputs? Yes, by generating random test inputs.

Random Test Function

Using generators, we can write a random test function:

def test[T](g: Generator[T], numTimes: Int = 100)
    (test: T => Boolean): Unit = {
        for (i <- 0 until numTimes) {
            val value = g.generate
            assert(test(value), ”test failed for ”+value)
        }
        println(”passed ”+numTimes+” tests”)
    }

// Usage:
test(pairs(lists, lists)) {
    case (xs, ys) => (xs ++ ys).length > xs.length // passes for non-empty lists, fails if one list is empty
}

ScalaCheck tool

The idea of these random generators and random tests is used in the ScalaCheck tool. ScalaCheck is a library written in Scala and used for automated property-based testing of Scala or Java programs.

Shift in viewpoint: Instead of writing tests, write properties that are assumed to hold.

forAll { (l1: List[Int], l2: List[Int]) =>
    l1.size + l2.size == (l1 ++ l2).size
}

It can be used either stand-alone or as part of ScalaTest. See ScalaCheck tutorial on the course page.