# How QuickCheck generates random functions

Posted on December 14, 2016 by Kwang Yul Seo
Tags: QuickCheck, test

In QuickCheck, test data is produced by test generators whose types are of the form `Gen a`. `Gen a` is a generator for values of type `a`. A type can define a default test data generator by defining an instance of the class `Arbitrary`:

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

We can define instances of `Arbitrary` using the combinators provided by QuickCheck. For example, the instances of `Bool` and `Ordering` are defined using `choose` and `elements` respectively. `choose` generates a random element in the given inclusive range and `elements xs` generates an arbitrary element of the list `xs`.

``````instance Arbitrary Bool where
arbitrary = choose (False,True)
shrink True = [False]
shrink False = []

instance Arbitrary Ordering where
arbitrary = elements [LT, EQ, GT]
shrink GT = [EQ, LT]
shrink LT = [EQ]
shrink EQ = []``````

Simple and easy! But how about a function? Can we generate a function in the same way? The answer is surprisingly yes, but you need another type class named `CoArbitrary`.

Before explaining how `CoArbitrary` works, we need to check how `Gen` is defined:

``````-- | A generator for values of type @a@.
newtype Gen a = MkGen{
unGen :: QCGen -> Int -> a -- ^ Run the generator on a particular seed.
-- If you just want to get a random value out, consider using 'generate'.
}``````

Internally, `Gen a` is a function which takes 2 arguments (`QCGen` and `Int`) and returns `a`. Here `QCGen` is a newtype wrapper around either `StdGen` or `TFGen`.

So `Gen (a -> b)` expands to `QCGen -> Int -> a -> b`. By reordering parameters, this is equivalent to `a -> Int -> QCGen -> b`, which represents `a -> Gen b`. Thus by defining

``promote :: (a -> Gen b) -> Gen (a->b)``

we can produce a generator for a function type, provided that we can construct a generator for the result type which somehow depends on the argument value.

So we need `coarbitrary` which modifies a generator in a way depending on its first parameter.

``````class CoArbitrary a where
coarbitrary :: a -> Gen b -> Gen b``````

To actually define an instance of `CoArbitrary`, we need a helper function `variant`, which perturbs the generator. It creates a new generator that produces different pseudo-random results than the original.

``````-- | Modifies a generator using an integer seed.
variant :: Int -> Gen a -> Gen a``````

Now we can define instances of `CoArbitrary`.

``````instance CoArbitrary Bool where
coarbitrary False = variant 0
coarbitrary True = variant 1

instance CoArbitrary a => CoArbitrary (Maybe a) where
coarbitrary Nothing  = variant 0
coarbitrary (Just x) = variant 1 . coarbitrary x``````

With all the pieces in place, we can finally define an `Arbitrary` for the function type `a -> b`:

``````instance (Coarbitrary a, Arbitrary b) => Arbitrary (a -> b) where
arbitrary = promote (\a -> coarbitrary a arbitrary)``````

To see how this works:

1. `\a -> coarbitrary a arbitrary` has type `a -> Gen b`
2. `promote` has type `(a -> Gen b) -> Gen (a->b)`
3. So, the entire expression has type `Gen (a->b)`

The current implementation of QuickCheck is a bit different as it is generalized to `Monad`, but When `m` is the function instance of `Monad`, `promote` is the same as we derived here.

``promote :: Monad m => m (Gen a) -> Gen (m a)``