haskell - 从 The Haskell Road to logic 的子字符串练习

Question

我最近开始阅读 Keets Doets 和 Jan van Eijck 合着的《通往逻辑、数学和编程的 Haskell 之路》一书(非常非常好的书)。

在其中一个练习中，任务是定义子字符串:我的解决方案有效并且比作者的要短得多，但是我并不妄想谁是更好的逻辑学家。

那么，我错过了什么:

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)

亲切的问候奥克

Answer 1

因为我想试试 QuickCheck 对于我自己在一个更大的项目中，这对我来说是一个很好的锻炼。 QuickCheck 是一个库，可以在生成的测试用例的属性中自动测试您的函数。您也可以创建自己的生成器，但我在这里没有这样做。

首先，我使用 cabal install QuickCheck 安装了 QuickCheck。我通过 import Test.QuickCheck 导入了模块，然后定义了属性:

prop_substring xs ys = substring xs ys == substring' xs ys

如果将此属性提供给 QuickCheck，将生成参数 xs 和 ys 作为 String。它将检查该属性是否为 True，这在本例中应该发生，因为两个 substring 函数当然应该返回相同的结果。

为了快速检查函数，我使用了verboseCheck prop_substring。这将根据 100 个生成的测试用例对其进行检查。第一个结果是:

Failed:
""
""
*** Failed! Falsifiable (after 1 test):
""
""

所以:不，这两个函数不一样。这是因为在你的函数 substring 中，如果第一个参数为空，你不会测试它是一个子字符串的基本情况，所以我添加了一行:

substring [] ys = True

然后，我又测试了一遍。下面是最后两个示例生成的测试用例:

Passed:
"C8Q<r6\195@\v_\195\DC1\170"
"E\219\DLE"
Passed:
"$ I\SYN\232\164\EOT9\182Ldah\255\173\DC2-B\DC2\SUBuF|\235iQ\236l\vS129\237x?}\187\229C\SYNUVUc/3bO7mE\ESCHB7V\DEL\FSM\EM\202^\162!\GS\DC3\\\nja\201\ESC\ENQOi"
"&?\USx>{\147\DC4g\171\EM\240Ha%\"C\ETX \SI\FS=\DC2\214V%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 的更多信息，请参见 outdated manual .例如，您可以告诉 QuickCheck 您想要一定数量的 True 测试用例，而不是成功测试用例的总数(当两个 substring 函数都产生结果时也会成功在 False)。