First, we download and build FsCheck. Then, in the F# interactive shell, (or an .fsx file), we run the following commands.
#I "/home/dave/lib/fsharp/fscheck" #r "FsCheck.dll"
This sets the load path to where I built the FsCheck dll, and references the dll. The FsCheck Quick Start and documentation have a lot more information than I am about to give...
First, we need a property to test. Since this is a sort function, we would like to see that the data is sorted. We need a function that given an array of data, sorts it, and checks if it is sorted. To keep things easier for now, we will use an integer array. Also, I have learned the hard way to make the tests fail first.. so this first version will be a bad test.
let prop_is_sorted (data:int ) = let N = Array.length data [|1..N-1|] |> Array.forall (fun i -> data.[i] >= data.[i-1])
This function takes an array of data, and checks that each element should be after the one before it. But, we didn't sort yet, so it should fail on some data. Let's run it to find out.
> Check.Quick prop_is_sorted;; Falsifiable, after 3 tests (3 shrinks) (StdGen (544801007,295317223)): [|1; 0|] val it : unit = ()
The test framework generated three different test cases. Two passed, and the third failed. Also, the framework shrank the failing test case three times, reducing the size of the data set that caused the failure. Shrinking doesn't always find a smaller data set, but when it does, it narrows the range of possible causes of the problem.
Let's update the test function to call our sort function, before checking if the array is sorted.
let prop_is_sorted (data:int ) = let N = Array.length data sort data [|1..N-1|] |> Array.forall (fun i -> data.[i] >= data.[i-1])
And running it gives us...
> Check.Quick prop_is_sorted;; Ok, passed 100 tests. val it : unit = ()
That is great! Except we don't know what kind of data really went into the tests... FsCheck provides ways to get some insight into the data going into the test. In this case, the default generators are probably doing a good enough job, but more complex cases will require more care.
A bad sort function could still pass this test. Perhaps a function that given an array of length N, returns an array with the numbers from 1 to N. We should write more tests on other properties of a sort function to make sure that our sort is doing what it is supposed to. In this case, we have a simple test we can use ... regression test against the system sort.
let prop_compare_with_system (data:int) = let a = Array.sort data // out of place sort data // in place a = data
This test passes again with 100 successes, and doesn't pass if we give a faulty sort function.
This type of randomized testing is a nice alternative to unit testing. In some cases, it is much less verbose, and it can generate test cases that I would never think of trying myself.
Now that we have some tests in place, we can implement some of the more advanced tweaks to the quicksort algorithm...