A QuickCheck Tutorial: Generators

QuickCheck is a Haskell library for testing properties using randomly generated values. It's one of the most popular Haskell libraries and part of the reason why functional programming has mattered.

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:

import Prelude hiding (reverse)

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> import Test.QuickCheck
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! Falsified (after 5 tests and 4 shrinks):
[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:

generate :: Gen a -> IO a

Let's run arbitrary to generate values of some basic types that have an instance of Arbitrary:

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 choose:

import Test.QuickCheck

...

dice :: Gen Int
dice =
  choose (1, 6)

And roll it:

ghci> generate dice
5

We can also generate a Bool with choose (in fact, this was QuickCheck's default generator for Bool before switching to a faster implementation using chooseEnum):

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 k from 0 to 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 nodes and 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

But 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 sized combinator:

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 nodes and edges functions so that the tests pass?

ghci> quickCheck prop_OneMoreNodeThanEdges
+++ OK, passed 100 tests.

All of the examples were tested with GHC 9.6.4 and QuickCheck 2.14.3. For more information, see the QuickCheck manual