Làm cách nào để kiểm tra chức năng bậc cao hơn bằng QuickCheck?

Question

Tôi có hàm bậc cao hơn mà tôi muốn thử nghiệm, và một trong các thuộc tính tôi muốn kiểm tra là chức năng của nó với các hàm được truyền vào. Ví dụ minh họa, đây là ví dụ:

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

Ý tưởng gần như là đây là trình tạo mẫu. Tôi sẽ bắt đầu với một đơn a, tạo một danh sách singleton gồm [a], sau đó tạo danh sách mới [a] cho đến khi vị từ bảo tôi dừng lại. Một cuộc gọi có thể trông như thế này:

gen init next stop 

nơi

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

Dưới đây là tài sản tôi muốn thử nghiệm:

Trên bất kỳ cuộc gọi đến gen init next stop, gen lời hứa không bao giờ vượt qua một danh sách trống đến next.

Tôi có thể kiểm tra thuộc tính này bằng QuickCheck và nếu có, làm cách nào?

Answer 1

Trong khi nó sẽ giúp đỡ nếu bạn đã thực hiện gen, tôi đoán rằng nó đi một cái gì đó như thế này:

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

Thuộc tính bạn muốn kiểm tra là next không bao giờ được cung cấp một danh sách trống . Một trở ngại để kiểm tra điều này là bạn muốn kiểm tra bất biến vòng lặp bên trong bên trong gen, vì vậy điều này cần phải có sẵn từ bên ngoài. Chúng ta hãy sửa đổi gen trở về thông tin này:

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

Chúng tôi sử dụng second từ Control.Arrow. Bản gốc gen có thể dễ dàng xác định theo genWitness:

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

Nhờ đánh giá lười biếng này sẽ không cho chúng ta nhiều chi phí. Quay lại tài sản! Để bật hiển thị các hàm được tạo từ QuickCheck, , chúng tôi sử dụng mô-đun Test.QuickCheck.Function. Mặc dù không cần thiết ở đây, thói quen tốt là để định hình bất động sản: chúng tôi sử dụng danh sách Int s thay vì cho phép giới hạn đơn cấu hình biến chúng thành danh sách đơn vị. Bây giờ chúng ta nêu tài sản:

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 

Chúng ta hãy thử chạy nó với QuickCheck:

ghci> quickCheck prop_gen 

Something dường như vòng lặp ... Có tất nhiên: gen vòng nếu stop trên danh sách từ next không bao giờ là True!Hãy để chúng tôi thay vì cố gắng nhìn vào tiền tố hữu hạn của các dấu vết đầu vào thay vì:

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) 

Chúng tôi hiện nhanh chóng có được aa phản ví dụ:

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

Chức năng thứ hai là lập luận next, và nếu nó trả về danh sách trống, thì vòng lặp trong gen sẽ cung cấp cho next danh sách trống.

Tôi hy vọng điều này sẽ trả lời câu hỏi này và nó cung cấp cho bạn một số thông tin chi tiết về cách kiểm tra các hàm bậc cao hơn bằng QuickCheck.

Answer 2

Có thể có hương vị xấu để lạm dụng điều này, nhưng QuickCheck không không hoạt động nếu nó ném ngoại lệ. Vì vậy, để kiểm tra, chỉ cần cung cấp cho nó một chức năng ném một ngoại lệ cho trường hợp trống. Thích ứng với câu trả lời của danr:

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 

Kỹ thuật này không yêu cầu bạn sửa đổi gen.