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

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

:

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

:

```
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 is QuickCheck's default generator for `Bool`

):

```
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 QuickCheck 2.8.1. For more information, see the QuickCheck manual,