A QuickCheck Tutorial: Generators
Tags: haskell, programming, functional
Published: 2024-03-11 21:37:43

Learn how to use QuickCheck’s combinators to create simple generators of random values. From reversing lists to rolling dice and crafting generators for your data types, this tutorial will enhance your programming skills and help you get started with property-based testing in Haskell. This popular post was originally written in 2015 and updated in January 2024 to reflect QuickCheck library changes up to the most recent version (2.14.3) as well as other minor fixes.

[QuickCheck][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][hfpm].

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:

```haskell
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:

```haskell
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):

```haskell
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:

```haskell
class Arbitrary a where
  arbitrary :: Gen a
  ...
```

If we have a generator, we can run it with `generate`:

```haskell
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:

```haskell
choose :: Random a => (a, a) -> Gen a
```

Let's define a dice with `choose`:

```haskell
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`):

```haskell
arbitraryBool :: Gen Bool
arbitraryBool =
  choose (False, True)
```

As another example, we can use `sized` to construct generators that depend on a size parameter:

```haskell
sized :: (Int -> Gen a) -> Gen a
```

Let's take a look at how QuickCheck generates lists:

```haskell
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:

```haskell
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:

```haskell
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:

```haskell
nodes :: Tree a -> Int
...
```

Or the number of edges:

```haskell
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:

```haskell
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:

```haskell
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:

```haskell
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][quickcheck-2.14.3]. For more information, see the
[QuickCheck manual][quickcheck-manual]
[hfpm]: https://doi.org/10.1093/nsr/nwv042
[quickcheck]: https://hackage.haskell.org/package/QuickCheck
[quickcheck-2.14.3]: https://hackage.haskell.org/package/QuickCheck-2.14.3
[quickcheck-manual]: https://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html