如何使用 QuickCheck 来测试函数是否终止？

Question

我想使用 QuickCheck 来测试一个函数以确保它终止（没有无限递归，没有抛出异常等）。这就是我现在所做的：

f :: Int -> Int -> Int

prop_fTerminates :: Int -> Int -> Bool   -- say
prop_fTerminates x y = f x y `seq` True

是否有更好的（更具表现力和地道的）方式？

Answer 1

这是halting problem。没有算法能够告诉您函数是否终止。

特别是，如果您愿意等待足够长的时间，您可能能够得到肯定的结果（即如果函数确实终止，这个命题会告诉您）。但是光是等待，你永远不知道这个函数没有终止和这个函数还没有终止。

的区别

您可以实施检查，例如此函数是否在时间 T 终止，这可能适合您的需要。

---

编辑 正如所写，您的函数没有满足您的要求。考虑

> let f = 1:f
> f `seq` True
True

原因是 seq 的计算结果仅为 weak head normal form。相反，您可以使用 deepseq 来深入评估数据结构，

> import Control.DeepSeq (deepseq)
> f `deepseq` True
* never returns *

Answer 2

我可能不会打扰，我只是测试其输出的其他属性。

任何以任何方式检查 f x y 输出的 属性 都将执行 至少 与 prop_fTerminates 一样多的终止检查]，那么为什么要浪费时间加倍检查呢？

如果出于某种原因 "f x y terminates" 是您唯一可以测试 f 的 属性，那么您得到的似乎是合理的。