How can I test a higher-order function using QuickCheck?

Question

I have a higher-order function that I want to test, and one of the properties I want to test is what it does with the functions that are passed in. For purposes of illustration, here is a contrived example:

gen :: a -> ([a] -> [a]) -> ([a] -> Bool) -> a

The idea is roughly that this is an example generator. I'm going to start with a single a, create a singleton list of [a], then make new lists of [a] until a predicate tells me to stop. A call might look like this:

gen init next stop

where

init :: a
next :: [a] -> [a]
stop :: [a] -> Bool

Here's the property I'd like to test:

On any call to gen init next stop, gen promises never to pass an empty list to next.

Can I test this property using QuickCheck, and if so, how?

Here's a related property: "For any non-empty input, next will produce a non-empty output". You might be interested in testing this instead, or in addition to, the property you mention. — John L
@JohnL Indeed so! But that's a property of next, not gen, and next is first-order, so I know how to test it. — Norman Ramsey

danr danr · Accepted Answer · 2012-03-13T16:13:39

While it would help if you gave the implementation of gen, I am guessing that it goes something like this:

gen :: a -> ([a] -> [a]) -> ([a] -> Bool) -> a
gen init next stop = loop [init]
  where
    loop xs | stop xs   = head xs
            | otherwise = loop (next xs)

The property you want to test is that next is never supplied an empty list. An obstacle to test this is that you want to check an internal loop invariant inside gen, so this needs to be available from the outside. Let us modify gen to return this information:

genWitness :: a -> ([a] -> [a]) -> ([a] -> Bool) -> (a,[[a]])
genWitness init next stop = loop [init]
  where
    loop xs | stop xs   = (head xs,[xs])
            | otherwise = second (xs:) (loop (next xs))

We use second from Control.Arrow. The original gen is easily defined in terms of genWitness:

gen' :: a -> ([a] -> [a]) -> ([a] -> Bool) -> a
gen' init next stop = fst (genWitness init next stop)

Thanks to lazy evaluation this will not give us much overhead. Back to the property! To enable showing generated functions from QuickCheck, we use the module Test.QuickCheck.Function. While it is not strictly necessary here, a good habit is to monomorphise the property: we use lists of Ints instead of allowing the monomorphism restriction making them to unit lists. Let us now state the property:

prop_gen :: Int -> (Fun [Int] [Int]) -> (Fun [Int] Bool) -> Bool
prop_gen init (Fun _ next) (Fun _ stop) =
    let trace = snd (genWitness init next stop)
    in  all (not . null) trace

Let us try the running it with QuickCheck:

ghci> quickCheck prop_gen

Something seems to loop... Yes of course: gen loops if stop on the lists from next is never True! Let us instead try to look at finite prefixes of the input trace instead:

prop_gen_prefix :: Int -> (Fun [Int] [Int]) -> (Fun [Int] Bool) -> Int -> Bool
prop_gen_prefix init (Fun _ next) (Fun _ stop) prefix_length =
    let trace = snd (genWitness init next stop)
    in  all (not . null) (take prefix_length trace)

We now quickly get a a counter-example:

385
{_->[]}
{_->False}
2

The second function is the argument next, and if it returns the empty list, then the loop in gen will give next an empty list.

I hope this answers this question and that it gives you some insight in how to test higher-order functions with QuickCheck.

How can I test a higher-order function using QuickCheck?

2 Answers