Introduction to ScalaCheck, Part 2 (A more complicated example)

“But I was trying to think why I don’t use QuickCheck — which is a very nice tool — more. I think it’s because the situations that cause me trouble are ones that I would find it difficult to generate test data for.”

Simon Peyton Jones, in the book, Coders at Work

In this lesson I’ll share a non-trivial example of how I used ScalaCheck to test a function I wrote recently.

While working on a Scala/FP application, I needed to create a function that reduced duplicate occurrences of a value in a list down to a single value. More accurately, given (a) a list, and (b) a value to look for, the purpose of the function is to retain the first occurrence of that element, and remove all subsequent occurrences of that element. I named this function, dropAllButFirst.

As an example of how this works, imagine that you have this list:

val xs = List(1, 2, 3, 2, 4, 2, 5)

With this list, I can use dropAllButFirst to create a new list that keeps the first occurrence of the number 2 and removes all subsequent occurrences like this:

val xss = dropAllButFirst(xs, 2)

When I apply dropAllButFirst as shown, xss should have this data:

List(1, 2, 3, 4, 5)

Testing with ScalaTest or JUnit

If I was going to test dropAllButFirst with ScalaTest or JUnit — and assuming that I want to keep looking for the number 2 — the first thing I’d do is think about what sample lists I should test with. When I do that, I come up with a series of test lists like these:

List()
List(1)
List(1,2)
List(1,2,2)
List(1,2,2,3)
List(1,2,2,3,2)
List(2)
List(2,1)
List(2,1,2)
List(2,1,2,3)
List(2,1,2,3,2)

Can you think of any other lists I should test against? That’s a little bit of a problem with the traditional ScalaTest/JUnit approach: Have you really thought of every possible set of data to test your function with?

Testing with ScalaCheck

While that’s probably your first thought when working with unit tests, you’ll find that your first thought when using ScalaCheck is quite different. With ScalaCheck, the first thing you think is, “What general statements or observations can I make about this function that are always true?” I find that this thought process feels more like writing a test specification (or requirements specification) than writing a unit test.

A first observation about `dropAllButFirst`

When I thought about dropAllButFirst, the first general observation that came to mind is:

1. If the element you want to drop is not in the input list, the resulting list should be exactly the same as the input list

Using my ScalaTest/JUnit test data as an example, this means that if dropAllButFirst gets this list as an input:

List(1)

it should return the exact same list as an output. Using just this one list as an example, I can express this general property in Scala code like this:

val xs = List(1)
val result = dropAllButFirst(xs, 2)
result == xs

If that last line doesn’t return true, there’s something wrong with my function.

(I’ll demonstrate how to write this property more generally with ScalaCheck in a few moments.)

A second observation about `dropAllButFirst`

The second general observation I can make about dropAllButFirst is similar to the first one:

2. If only one occurrence of the element you want to drop is in the input list, the resulting list should be the same as the input list

I can test this statement just like the first observation, so I won’t say anything else about it.

A third observation about `dropAllButFirst`

Next, I begin thinking about lists that contain more than one instance of the value I’m searching for, and I come up with this observation:

3. If more than one occurrence of the element you want to drop is in the input list, then: (A) the first element should remain in its original position; (B) all other occurrences of that element should be dropped; (C) all other elements in the list should be as they were.

Parts A and B of that statement are easy to test — and I’ll show how to do that shortly — but I initially found Part C to be hard to implement without using dropAllButFirst to prove itself(!). This is a potential problem with using random data. For instance, with static test data you know that this list:

List(1,2,2,3)

should be reduced to this:

List(1,2,3)

But when you get 100 random lists like this:

List(1,2,3,2,4,5,2,6)
List(1000,-2347896,9876543,1133456)

you have no idea what you’re going to get as input, so you have to find different ways to prove that the output list is correct.

Implementing the third observation

The way I implemented the third observation was to think about tests that I could actually write in Scala. After a little trial and error, I came up with a set of sub-tests to implement each phrase of that observation. Specifically, given any input list that has more than one occurrence of the element I want to search for, after running dropAllButFirst:

A. The first element should remain in its original position. I can implement this by finding the first occurrence in both the “before” and “after” lists using the List class indexOf method. B. All other occurrences should be dropped. Because the first test confirms that the first occurrence is in the proper location, this test only needs to confirm that the “after” list contains only one occurrence of the value I want to remove. I can do this with the List class count method. C. All other elements in the list should be as they were. This is a more complicated algorithm that I’ll describe next.

There are other ways to write an algorithm for this third test, but the method I came up with is to split the input and result lists at the point of the first occurrence, and work with those sub-lists. For instance, given this input list:

val input = List(1, 2, 3, 2, 4, 2, 5)

the correct result should be:

val result = List(1, 2, 3, 4, 5)

If I split the input list at the location of the first 2, I get these two lists:

val inputBefore = List(1)
val inputAfter  = List(3, 2, 4, 2, 5)

Next, my algorithm is supposed to remove all remaining 2 values in inputAfter, so I can use filter to achieve that effect:

val inputAfterFilter = inputAfter.filter(_ == 2)

That gives me:

val inputAfterFilter = List(3, 4, 5)

Therefore, splitting my “input” list into two sub-lists, and removing the matches from the second sub-list results in these two lists:

val inputBefore = List(1)
val inputAfterFilter = List(3, 4, 5)

Now I can do the same thing with the result list. Starting with this result, which I know to be correct:

val result = List(1, 2, 3, 4, 5)

I split it at the location of the 2, and get these two sub-lists:

val resultBefore = List(1)
val resultAfter  = List(3, 4, 5)

If everything works properly, I can then compare those two lists to these two lists:

val inputBefore      = List(1)
val inputAfterFilter = List(3, 4, 5)

If, for all possible List[Int], inputBefore equals resultBefore, and inputAfterFilter equals resultAfter, I can be sure that dropAllButFirst works.

Discussion

Item C shows a problem with ScalaCheck: I basically had to create a second version of my algorithm to prove that the first version of my algorithm works properly. (I haven’t shown its source code yet, but dropAllButFirst uses a recursive algorithm.)

There may be other ways that you can write tests to feel comfortable about Item C, but this is the best “proof” I came up with. There are other less-extensive ways that are easier to implement that will give you a pretty high level of confidence that dropAllButFirst works as intended, but they didn’t give me as much confidence as this approach.

The ScalaCheck thought process

While property tests can occasionally be hard to implement, I really like the ScalaCheck thought process. In several cases, such as with dropAllButFirst, it made me think harder.

In fact, as I was working on these property tests I thought, “Hmm, dropAllButFirst is really a special implementation of a more general algorithm. For instance, what if I ever want to keep the first two elements, and then drop all of the rest? Or the first three elements, etc.” The process of thinking more generally about the properties of dropAllButFirst made me think of that, and I don’t know if I would have had that same thought while writing unit tests.

Source code

The source code for this project is at the same URL as the previous lesson:

github.com/alvinj/FPScalaCheck

The ScalaCheck code

At this point the best thing I can do is show the code I used to implement those property tests using the ScalaCheck syntax. Excluding the import statements, boilerplate class code, and the List[Int] generators I created for these tests, here’s the property test that implements the three observations I made about dropAllButFirst:

object DropAllButFirstSpec extends Properties("DropAllButFirstSpec") {

    val NUM_TO_DROP = 2

    property("dropAllButFirstIntLists") = forAll(GenSeq.g1to5) { input: List[Int] =>

        // run `dropAllButFirst`
        val result = ListUtils.dropAllButFirst(input, 2)

        // start the tests
        val numMatches = input.count(_ == NUM_TO_DROP)
        if (numMatches == 0) {
            /**
              * OBSERVATION 1: If the element you want to drop is not in the input list,
              * the resulting list should be the same as the input list
              */
            input == result
        } else if (numMatches == 1) {
            /**
              * OBSERVATION 2: If only one occurrence of the element you want to drop
              * is in the input list, the resulting list should be the
              * same as the input list
              */
            input == result
        } else {
            /**
              * OBSERVATION 3: If more than one occurrence of the element you want
              * to drop is in the input list, then: (a) the first element should
              * remain in its original position; (b) all other occurrences should
              * be dropped; (c) all other elements in the list should be as they were.
              */

            // (a) “the first element should remain in its original position.”
            val element1PositionOriginal = input.indexOf(NUM_TO_DROP)
            val element1PositionFinal = result.indexOf(NUM_TO_DROP)

            // (b) “all other occurrences should be dropped.” it's enough to
            // test that there is only one occurrence in `result`
            val numOccurrencesInResult = result.count(_ == NUM_TO_DROP)

            // (c) “all other elements in the list should be as they were.”
            val locationOfFirstOccurrenceInInput = input.indexOf(NUM_TO_DROP)
            val (inputBefore, inputAfter) = input.splitAt(locationOfFirstOccurrenceInInput)
            // splitAt retains the 'split' element as the first element of the "after" list.
            // therefore, only look at the tail of the "after" list.
            val inputAfterTail = inputAfter.tail
            val inputAfterFiltered = inputAfterTail.filter(_ != NUM_TO_DROP)

            val locationOfFirstOccurrenceInResult = result.indexOf(NUM_TO_DROP)
            val (resultBefore, resultAfter) = result.splitAt(locationOfFirstOccurrenceInResult)
            val resultAfterTail = resultAfter.tail

            // run all of the “Observation 3” property tests
            (
                element1PositionOriginal == element1PositionFinal &&   //property 3.a
                numOccurrencesInResult == 1                       &&   //property 3.b
                inputBefore == resultBefore                       &&   //property 3.c
                inputAfterFiltered == resultAfterTail                  //property 3.c
            )

        }
    }

}

Hopefully most of that code is readable. If you’re new to ScalaCheck, this line probably needs the most explanation:

property("dropAllButFirstIntLists") = forAll(GenSeq.g1to5) { input: List[Int] =>

In this case I created a ScalaCheck generator named GenSeq.g1to5 that generates lists of integers in a manner that I thought was best to stress-test dropAllButFirst. I’ll discuss that shortly.

Another point worth mentioning is that the splitAt method retains the element you’re splitting on — 2 in this case — in the second list, so you need to drop that element from the second list. It’s always the head element of that list, so you can easily drop it by just taking the tail of that list:

val inputAfterTail = inputAfter.tail

Finally, a property test wants a single, final Boolean value as a result, and I achieve that by running all of the “Observation 3” tests at the end:

(
    element1PositionOriginal == element1PositionFinal &&   //property 3.a
    numOccurrencesInResult == 1                       &&   //property 3.b
    inputBefore == resultBefore                       &&   //property 3.c
    inputAfterFiltered == resultAfterTail                  //property 3.c
)

Creating a `List[Int]` generator

There are two critical skills involved in working with ScalaCheck:

Writing properties (what I call “property tests”)
Writing generators

Generators are the functions that generate the random data that is used to test your code. There are many default generators, such as the generator that created random Int values for the test in the previous lesson. However, you’ll often need to create your own, such as when you need to test against your own custom case classes.

If you want to learn a lot about writing generators, I encourage you to read ScalaCheck: The Definitive Guide, but in this section I’ll show how I wrote a few List[Int] generators to test dropAllButFirst.

I could easily write 20-50 pages on this topic, so as a bit of a warning, I only cover generators here at a high level.

The default `List[Int]` generator

First, I tried to use the default List[Int] generator like this:

property("dropAllButFirstIntLists") = forAll { input: List[Int] =>

The problem with it is that I need to make sure my tests usually have at least one 2 in them, but because this generator creates Int values from Int.MinValue to Int.MaxValue, that rarely happens.

Generate values in a range

One of the better generators I created looks like this:

val g1to5: Gen[List[Int]] = Gen.containerOf[List,Int](Gen.choose(1, 5))

This creates lists of random lengths by evenly distributing the numbers 1 to 5. Here are some sample values from this generator:

input: List()
input: List(3)
input: List(2, 1)
input: List(4, 3, 5)
input: List(1, 3, 3, 5)
input: List(3, 2, 2, 2, 2, 3, 4)
input: List(1, 1, 1, 2, 5, 4, 2, 4, 5, 2)
input: List(5, 1, 2, 1, 5, 5, 2, 4, 3, 3, 5, 2, 5, 5)

Some of the lists it generates are much longer than what I’ve shown here, which is good or bad, depending on your needs.

Generate values using a frequency distribution

I also created a generator that let me control how many 2’s were generated in comparison to other values. This is a two-step process. In the first step, you set up your frequency distribution. Here I declare that I want four times as many 2’s as I want other integers:

val favorTwos: Gen[Int] = Gen.frequency(
    (1, 1),
    (4, 2),   //4x the number of 2s
    (1, 3),
    (1, 4),
    (1, 5)
)

In the second step, I create a generator that generates List[Int] values:

genMostlyTwos: Gen[List[Int]] = Gen.containerOf[List,Int](favorTwos)

Here is some sample data from this generator:

input: List()
input: List(2)
input: List(2, 2, 1)
input: List(2, 2, 2, 2)
input: List(3, 1, 5, 2, 5, 2)
input: List(3, 2, 1, 2, 3, 2, 2, 2)
input: List(2, 4, 3, 2, 5, 2, 1, 4, 1)

As with the previous generator, the lists it generates are much longer than what I’ve shown, which is good or bad, depending on your needs.

Another way to control the distribution

This third example shows another way I came up with to control the distribution of Int values. First, I created a List[Int] like this:

val littleList: List[Int] = scala.util.Random.shuffle(List(1,2,3,4,5,6,2,7,8,9))

Then I use the Gen.someOf helper function to create this List[Int] generator:

val littleListGen: Gen[List[Int]] = Gen.someOf(littleList).map(_.toList)

One of the best features of this approach is that it creates lists that contain ten elements or less:

input: List(8)
input: List(5, 8, 6)
input: List(4, 8, 9, 6)
input: List(4, 7, 5, 3, 2, 8)
input: List(2, 5, 9, 3, 2, 6, 8, 4)
input: List(8, 7, 9, 3, 2, 6, 1, 4, 5)
input: List(2, 7, 9, 3, 2, 6, 1, 4, 5, 8)

More on generators

As I mentioned, I could easily write dozens of pages about ScalaCheck generators. Rather than doing that, I encourage you to clone my project from Github, then (a) un-comment the println statement inside the DropAllButFirstSpec_IntLists property test, and then (b) experiment and change the first line of code in the property test to use the different generators, like this:

property("dropAllButFirstIntLists") = forAll(GenIntSeq.g1to5) ...
property("dropAllButFirstIntLists") = forAll(GenIntSeq.genMostlyTwos) ...
property("dropAllButFirstIntLists") = forAll(GenIntSeq.littleListGen) ...

After that, experiment with the process to see the pros and cons of each approach, and see if you can create better generators.

Running the property test

When you run the “dropAllButFirstIntLists” property test with (a) your IDE or (b) from the SBT command line (with sbt test), you should see this result:

+ DropFirstSpec.dropAllButFirst_SeqOfInts: OK, passed 100 tests.

That tells you that this property test was tested with 100 random lists, and ScalaCheck didn’t find any problems.

One problem not found

Unless you create a generator to generate very large lists, one problem that ScalaCheck won’t find is that because my dropAllButFirst function isn’t tail-recursive, it will run into StackOverflow errors on large lists. I didn’t concern myself with this problem because I knew that I only wanted to use the function on small lists, but this is a potential problem with both ScalaCheck (and unit test frameworks).

Please clone my Github project to see the dropAllButFirst implementation.

One more note: Tests as specification

ScalaCheck: The Definitive Guide, makes a good observation that also describes this process well:

“While the idea of ‘tests as specification’ is to make your specification more test-centered, property-based testing goes in the opposite direction by making your tests more specification-like. It does so by generalizing tests to properties.”

The book further adds, “A specification is a definition of a program’s behavior in the general case.” In my view, that’s exactly what property tests are.

Summary

I hope these two chapters have given you a taste of how ScalaCheck works, including a glimpse of its pros and cons.

I find it easiest to learn something like this by experimenting with it, so I encourage you to clone my Github project and work with it as desired to become comfortable with it. In the project I also include additional property tests, so you can see even more examples. One of the tests works with pizza toppings and a List[Topping] generator so you can see something besides Int tests.