我最近开始阅读Keets Doets和Jan van Eijck的《The Haskell Road to Logic, Maths and Programming》(非常非常好的书)一书。
在其中一个练习中,任务是定义子字符串: 我的解决方案有效并且比作者短得多,但我并不妄想谁是更好的逻辑学家。
那么,我错过了什么:
prefix :: String -> String -> Bool
prefix [] y = True
prefix x [] = False
prefix (x:xs) (y:ys) = (x == y) && (prefix xs ys)
substring :: String -> String -> Bool
substring x [] = False
substring x (y:ys) | prefix x (y:ys) = True
| otherwise = substring x ys
-- Thought the answer provided was a bit overdone
substring' :: String -> String -> Bool
substring' [] ys = True
substring' (x:xs) [] = False
substring' (x:xs) (y:ys) = ((x==y) && (prefix xs ys)) || (substring' (x:xs) ys)
亲切的问候奥克
由于我想在一个更大的项目中为自己尝试QuickCheck,这对我来说是一个很好的练习。QuickCheck 是一个库,可以在生成的测试用例的属性中自动测试您的函数。您也可以创建自己的生成器,但我在这里没有这样做。
首先,我安装了 快速检查 与cabal install QuickCheck
.我通过import Test.QuickCheck
导入了模块,然后定义了属性:
prop_substring xs ys = substring xs ys == substring' xs ys
此属性,如果提供给快速检查,将生成参数xs
并ys
为String
。它将检查属性是否True
,在这种情况下应该发生这种情况,因为当然,两个substring
函数都应该返回相同的结果。
为了快速检查该功能,我使用了verboseCheck prop_substring
.这将根据 100 个生成的测试用例进行检查。第一个结果是:
Failed:
""
""
*** Failed! Falsifiable (after 1 test):
""
""
所以:不,这两个功能是不一样的。这是因为在您的函数中,substring
如果第一个参数为空,则不会测试它是子字符串的基本情况,因此我添加了一行:
substring [] ys = True
然后,我再次测试了它。下面是最后两个示例生成的测试用例:
Passed:
"C8Q<r6195@v_195DC1170"
"E219DLE"
Passed:
"$ ISYN232164EOT9182Ldah255173DC2-BDC2SUBuF|235iQ236lvS129237x?}187229CSYNUVUc/3bO7mEESCHB7VDELFSMEM202^162!GSDC3\nja201ESCENQOi"
"&?USx>{147DC4g171EM240Ha%"CETX SIFS=DC2214V%H"
+++ OK, passed 100 tests.
但这只有 100 次测试,那更多呢?您可以使用其他函数并使用其他参数。让我们尝试使用 100.000 个测试用例:
*Substring> quickCheckWith stdArgs { maxSuccess = 100000 } prop_substring
+++ OK, passed 100000 tests.
所以是的,似乎这两个函数都提供了相同的结果!虽然有两个缺点:第一个是 QuickCheck 不太可能生成两个带有substring
的字符串。由于它产生随机String
,它更有可能产生两个完全不同的String
。这可以通过创建自己的生成器来解决。第二个缺点是QuickCheck没有给你一个正式的证明。
第一个可以用属性进行分析。如果我们prop_substring
更改为:
prop_substring xs ys =
collect (substring xs ys) $
(substring xs ys == substring' xs ys)
然后我们收集结果,这样我们可以看到结果的百分比。对于 100.000,这是:
*Substring> quickCheckWith stdArgs { maxSuccess = 100000 } prop_substring
+++ OK, passed 100000 tests:
94% False
5% True
因此,大约有 5000 个返回True
.您还可以生成xs
和ys
,并为substring
函数提供参数xs
和xs++ys
或xs
和ys++xs
,以便仅测试True
情况。这两个选项都通过了 100.000 次测试,因此我们几乎可以假设这两个函数给出相同的结果。
有关快速检查的更多信息在有点过时的手册中。例如,您可以告诉 QuickCheck 您想要一定数量的True
测试用例,而不是成功测试用例的总数(当两个substring
函数都导致False
时也会成功)。