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?

Purposeless

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. – Laurettalaurette

@JohnL Indeed so! But that's a property of next, not gen, and next is first-order, so I know how to test it. – Purposeless

Answer 1

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.

Scherle

if you altered gen to gen :: Monad m => a -> ([a] -> m [a]) -> ([a] -> m Bool) -> m a, then you could put your witnessing code inside next (and stop), and not worry about sullying the implementation with such logging. – Simply

Wow. I was expecting to put some kind of wrapper around gen, but I'm not sure I want to have to muck up my nice clean gen with this extra gunk. I will look into it an get back to you. – Purposeless

@NormanRamsey: using @rampion's suggestion by just doing it monadic and then use the writer monad to do a trace wouldn't require too much gunk. Then next only needs to write its input to the writer monad. – Scherle

@NormanRamsey I believe the difficulty in testing is that the gen function is not so clean after all. Have you considered making the first argument a list instead of a single element? This would allow testing of this property MUCH easier, since you could just pass an empty list to test this condition instead of relying on the behavior of the next and stop functions in your test. – Jan

@Jan : How would that help? That would immediate violate the property. The property you really want to show is that the inner "loop", of which I have merely given an example implementation above, that next never gets an empty list, and these lists would come from next itself and possible combinations and rearrangements from inside the loop: that's what we must test. – Scherle

Answer 2

It is possibly in bad taste to abuse this, but QuickCheck does fail a function if it throws an exception. So, to test, just give it a function that throws an exception for the empty case. Adapting danr's answer:

import Test.QuickCheck
import Test.QuickCheck.Function
import Control.DeepSeq

prop_gen :: Int -> (Fun [Int] [Int]) -> (Fun [Int] Bool) -> Bool
prop_gen x (Fun _ next) (Fun _ stop) = gen x next' stop `deepseq` True
  where next' [] = undefined
        next' xs = next xs

This technique does not require you to modify gen.

Disharmonious

There's one problem with this: if the stop function never returns True, it'll loop forever. Instead of a QuickCheck provided function, the user needs to create a stop that's guaranteed to return True at some point. Short of a function like const True, this may be difficult to guarantee. – Laurettalaurette