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:
reverse :: [a] -> [a] reverse  =  reverse (x:xs) = reverse xs ++ [x]
We can define a property to check whether reversing a list (of integers) yields the same list or not:
prop_ReverseReverseId :: [Integer] -> Bool prop_ReverseReverseId xs = reverse (reverse xs) == xs
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):
prop_ReverseId :: [Integer] -> Bool prop_ReverseId xs = reverse xs == xs
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:
class Arbitrary a where arbitrary :: Gen a ...
If we have a generator, we can run it with
generate :: Gen a -> IO a
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:
choose :: Random a => (a, a) -> Gen a
Let's define a dice with
dice :: Gen Int dice = choose (1, 6)
And roll it:
ghci> generate dice 5
We can also generate a
choose (in fact, this is QuickCheck's default generator for
arbitraryBool :: Gen Bool arbitraryBool = choose (False, True)
As another example, we can use
sized to construct generators that depend on a size parameter:
sized :: (Int -> Gen a) -> Gen a
Let's take a look at how QuickCheck generates lists:
arbitraryList :: Arbitrary a => Gen [a] arbitraryList = sized $ \n -> do k <- choose (0, n) sequence [ arbitrary | _ <- [1..k] ]
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:
data Tree a = Tree a [Tree a] deriving (Show)
A rose tree is just a node and a list of trees. Here's a sample tree:
aTree :: Tree Int aTree = Tree 5 [Tree 12 [Tree (-16) ],Tree 10 ,Tree 16 [Tree 12 ]]
Given such a tree, we can ask for things such as the number of nodes:
nodes :: Tree a -> Int ...
Or the number of edges:
edges :: Tree a -> Int ...
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:
prop_OneMoreNodeThanEdges :: Tree Int -> Bool prop_OneMoreNodeThanEdges tree = nodes tree == edges tree + 1
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:
instance Arbitrary a => Arbitrary (Tree a) where arbitrary = do t <- arbitrary ts <- arbitrary return (Tree t ts)
But we wouldn't be able to guarantee that such a generator would ever stop. Thus, we need to use the
instance Arbitrary a => Arbitrary (Tree a) where arbitrary = sized arbitrarySizedTree arbitrarySizedTree :: Arbitrary a => Int -> Gen (Tree a) arbitrarySizedTree m = do t <- arbitrary n <- choose (0, m `div` 2) ts <- vectorOf n (arbitrarySizedTree (m `div` 4)) return (Tree t ts)
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.