子弦从哈斯克尔路练习逻辑

Question

我最近开始工作，通过我的方式通过书哈斯克尔逻辑，数学和编程通过Keets Doets &杨范Eijck（非常非常好的书）。

在其中一个练习中，我的任务是定义子字符串：我的解决方案的工作原理是 ，比作者的短得多，但我并不妄想谁是更好的Logician。

所以，我在想什么：

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是一个库，可以在生成的测试用例的属性中自动测试你的函数。你也可以创建你自己的发电机，但是我没有在这里做。

首先，我安装了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<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时都会成功）。