# QuickCheck

# Randomly generating data for custom types

The Arbitrary class is for types that can be randomly generated by QuickCheck.

The minimal implementation of Arbitrary is the arbitrary method, which runs in the Gen monad to produce a random value.

Here is an instance of Arbitrary for the following datatype of non-empty lists.

import Test.QuickCheck.Arbitrary (Arbitrary(..))
import Test.QuickCheck.Gen (oneof)
import Control.Applicative ((<$>), (<*>))

data NonEmpty a = End a | Cons a (NonEmpty a)

instance Arbitrary a => Arbitrary (NonEmpty a) where
    arbitrary = oneof [  -- randomly select one of the cases from the list
        End <$> arbitrary,  -- call a's instance of Arbitrary
        Cons <$>
            arbitrary <*>  -- call a's instance of Arbitrary
            arbitrary  -- recursively call NonEmpty's instance of Arbitrary

# Using implication (==>) to check properties with preconditions

prop_evenNumberPlusOneIsOdd :: Integer -> Property
prop_evenNumberPlusOneIsOdd x = even x ==> odd (x + 1)

If you want to check that a property holds given that a precondition holds, you can use the ==> operator. Note that if it's very unlikely for arbitrary inputs to match the precondition, QuickCheck can give up early.

prop_overlySpecific x y = x == 0 ==> x * y == 0

ghci> quickCheck prop_overlySpecific
*** Gave up! Passed only 31 tests.

# Declaring a property

At its simplest, a property is a function which returns a Bool.

prop_reverseDoesNotChangeLength xs = length (reverse xs) == length xs

A property declares a high-level invariant of a program. The QuickCheck test runner will evaluate the function with 100 random inputs and check that the result is always True.

By convention, functions that are properties have names which start with prop_.

# Checking a single property

The quickCheck function tests a property on 100 random inputs.

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

If a property fails for some input, quickCheck prints out a counterexample.

prop_reverseIsAlwaysEmpty xs = reverse xs == []  -- plainly not true for all xs

ghci> quickCheck prop_reverseIsAlwaysEmpty
*** Failed! Falsifiable (after 2 tests):                  

# Checking all the properties in a file

quickCheckAll is a Template Haskell helper which finds all the definitions in the current file whose name begins with prop_ and tests them.

{-# LANGUAGE TemplateHaskell #-}

import Test.QuickCheck (quickCheckAll)
import Data.List (sort)

idempotent :: Eq a => (a -> a) -> a -> Bool
idempotent f x = f (f x) == f x

prop_sortIdempotent = idempotent sort

-- does not begin with prop_, will not be picked up by the test runner
sortDoesNotChangeLength xs = length (sort xs) == length xs

return []
main = $quickCheckAll

Note that the return [] line is required. It makes definitions textually above that line visible to Template Haskell.

$ runhaskell QuickCheckAllExample.hs
=== prop_sortIdempotent from tree.hs:7 ===
+++ OK, passed 100 tests.

# Limiting the size of test data

It can be difficult to test functions with poor asymptotic complexity using quickcheck as the random inputs are not usually size bounded. By adding an upper bound on the size of the input we can still test these expensive functions.

import Data.List(permutations)
import Test.QuickCheck

longRunningFunction :: [a] -> Int
longRunningFunction xs = length (permutations xs)

factorial :: Integral a => a -> a
factorial n = product [1..n]

prop_numberOfPermutations xs =
    longRunningFunction xs == factorial (length xs)

ghci> quickCheckWith (stdArgs { maxSize = 10}) prop_numberOfPermutations

By using quickCheckWith with a modified version of stdArgs we can limit the size of the inputs to be at most 10. In this case, as we are generating lists, this means we generate lists of up to size 10. Our permutations function doesn't take too long to run for these short lists but we can still be reasonably confident that our definition is correct.