A QuickCheck Tutorial: Generators
In short, we can use functions to express properties about our programs and QuickCheck to test that such properties hold for large numbers of random cases.
For example, given a function to reverse the elements of a list:
We can define a property to check whether reversing a list (of integers) yields the same list or not:
And QuickCheck will generate 100 lists and test that the property holds for all of them:
ghci> quickCheck prop_ReverseReverseId +++ OK, passed 100 tests.
If we define a property to check whether reversing a list once yields the same list or not (which holds only for some lists):
QuickCheck will generate lists until it finds one that makes the property fail:
ghci> quickCheck prop_ReverseId *** Failed! Falsifiable (after 3 tests): [0,1]
This is a simple example, but it’s good enough for illustrating the basic idea behind testing real world Haskell libraries and programs using QuickCheck.
Now, a fundamental part of QuickCheck is random generation of values. Let’s take a look at some of the pieces involved in this process and some examples of how to generate our own random values.
To generate a random value of type
a, we need a generator for values of that type:
Gen a. The default generator for values of any type is
arbitrary, which is a method of QuickCheck’s
Arbitrary type class:
If we have a generator, we can run it with
arbitrary to generate values of some basic types that have an instance of
ghci> generate arbitrary :: IO Int 27 ghci> generate arbitrary :: IO (Char, Bool) ('m',True) ghci> generate arbitrary :: IO [Maybe Bool] [Just False,Nothing,Just True] ghci> generate arbitrary :: IO (Either Int Double) Left 7
Additionally, QuickCheck provides several combinators that we can use to generate random values and define our own instances of
Arbitrary. For instance, we can use
choose to generate a random element in a given range:
Let’s define a dice with
And roll it:
ghci> generate dice 5
We can also generate a
choose (in fact, this is QuickCheck’s default generator for
As another example, we can use
sized to construct generators that depend on a size parameter:
Let’s take a look at how QuickCheck generates lists:
Given a size parameter
n, QuickCheck chooses a
n, the number of elements of the list, and generates a list with
k arbitrary elements.
We can follow this pattern to construct generators for our own data types. Let’s use (rose) trees as an example of how to do this:
A rose tree is just a node and a list of trees. Here’s a sample tree:
Given such a tree, we can ask for things such as the number of nodes:
Or the number of edges:
The sample tree has 6 nodes and 5 edges, for instance:
ghci> nodes aTree 6 ghci> edges aTree 5
Given definitions for
edges, we can test that they satisfy the theorem that every tree has one more node than it has edges:
Tree a is not an instance of
Arbitrary yet, so QuickCheck doesn’t know how to generate values to check the property. We could simply use the
arbitrary generator for lists:
But we wouldn’t be able to guarantee that such a generator would ever stop. Thus, we need to use the
Given a size parameter
m, we generate a value of type
a, choose a number
n to be the number of trees in the list, and then generate
n trees using the
vectorOf combinator. We use the
div function to make sure that generation stops at some point.
Let’s test the generator:
ghci> generate arbitrary :: IO (Tree Int) Tree (-19) [Tree (-2) [Tree 15 ,Tree 28 ]] ghci> generate arbitrary :: IO (Tree Int) Tree 30 [Tree 15 ,Tree 19 [Tree 3 ,Tree (-28) ]] ghci> generate arbitrary :: IO (Tree Int) Tree (-11) [Tree (-6) [Tree (-6) ,Tree 1 ]]
Can you define the
edges functions so that the tests pass?
ghci> quickCheck prop_OneMoreNodeThanEdges +++ OK, passed 100 tests.