Am Dienstag 02 Februar 2010 23:03:48 schrieb Daniel Fischer:
Am Dienstag 02 Februar 2010 22:46:20 schrieb Joe Van Dyk:
Any chance anyone can show me how to write a QuickCheck test for this?
Joe
prop_binary_search :: Int -> [Int] -> Bool prop_binary_search x xs = let ys = sort xs in binary_search x ys == elemIndex x ys
ghci> quickCheck prop_binary_search +++ OK, passed 100 tests.
Ah, but: ghci> quickCheckWith (stdArgs { maxSuccess = 10000, maxDiscard = 1000, maxSize = 2000 }) prop_binary_search *** Failed! Falsifiable (after 8007 tests and 3 shrinks): -1 [-1,-1] Okay, does that mean my function is wrong? In this case, no, my test was wrong. I intended binary_search to be used only on *strictly* ascending lists, so change the test to import Data.IntSet (fromList, toAscList) prop_binary_search :: Int -> [Int] -> Bool prop_binary_search x xs = let ys = toAscList (fromList xs) in binary_search x ys == elemIndex x ys Now: ghci> quickCheckWith (stdArgs { maxSuccess = 10000, maxDiscard = 1000, maxSize = 2000 }) prop_binary_search +++ OK, passed 10000 tests. or perhaps a different test: prop_binary_search_2 :: Int -> [Int] -> Bool prop_binary_search_2 x xs = let ys = sort xs in case binary_search x ys of Nothing -> x `notElem` ys Just k -> x == ys !! k