Как я могу проверить функцию высшего порядка, используя QuickCheck? - PullRequest
Новая
       11

Как я могу проверить функцию высшего порядка, используя QuickCheck?

14 голосов
/ 13 марта 2012

У меня есть функция высшего порядка, которую я хочу протестировать, и одно из свойств, которые я хочу протестировать, - это то, что она делает с переданными функциями. Для иллюстрации приведу надуманный пример: 

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

Идея примерно в том, что это пример генератора. Я собираюсь начать с одного a, создать одноэлементный список [a], затем создать новые списки [a], пока предикат не скажет мне остановиться. Вызов может выглядеть так: 

gen init next stop

, где 

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

Вот свойство, которое я хотел бы проверить:

При любом вызове gen init next stop, gen обещает никогда не передавать пустой список next.

Можно ли проверить это свойство с помощью QuickCheck , и если да, то как?

Ответы [ 2 ]

10 голосов
/ 13 марта 2012

Хотя было бы полезно, если бы вы дали реализацию gen, я предполагая, что это выглядит примерно так: 

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

Свойство, которое вы хотите проверить, состоит в том, что next никогда не предоставляется пустой список Препятствием для проверки является то, что вы хотите проверить Внутренний цикл инвариант внутри gen, так что это должно быть доступно из снаружи. Давайте изменим gen чтобы вернуть эту информацию: 

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

Мы используем second из Control.Arrow . Оригинал gen легко определить в терминах genWitness:

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

Благодаря ленивой оценке это не даст нам много накладных расходов. Вернуться к недвижимость! Чтобы включить отображение сгенерированных функций из QuickCheck, мы используем модуль Test.QuickCheck.Function . Хотя это не является строго необходимым здесь, хорошая привычка мономорфизировать свойство: мы используем списки Int s вместо разрешения ограничение мономорфизма делает их списками единиц. Давайте теперь заявим собственность: 

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

Давайте попробуем запустить его с помощью QuickCheck: 

ghci> quickCheck prop_gen

Кажется, что-то зациклено ... Да, конечно: gen зацикливается, если stop на списки от next никогда не True! Вместо этого попробуем взглянуть на конечные префиксы входной трассы. вместо: 

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)

Теперь мы быстро получаем контрпример: 

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

Второй функцией является аргумент next, и если он возвращает пустой список, тогда цикл в gen выдаст next пустой список.

Я надеюсь, что это ответит на этот вопрос и даст вам некоторое представление как тестировать функции высшего порядка с помощью QuickCheck.

4 голосов
/ 14 марта 2012

Злоупотреблять этим, возможно, нехорошо, но QuickCheck не выполняет функцию, если выдает исключение. Итак, чтобы проверить, просто дайте ему функцию, которая выдает исключение для пустого регистра. Адаптация ответа данра: 

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

Для этой техники не требуется изменять gen.

...