如何在QuickCheck中得到好的（小的）收缩？

Question

我正在尝试在一些嵌套的列表上运行QuickCheck，类似于这样：

type Constraint = Text
data Value = Value [Constraint]
data Literal = Literal Value [Value]
type Formula = [Literal]

因此，一个公式是一个文字列表，每个文字包含一个谓词和一些参数；谓词/参数是以字符串形式表示的约束的析取值。这给我们提供了一个列表，其中包含了多个嵌套的列表，使得阅读起来有点费劲。

如果我的 QuickCheck 属性之一失败，我往往会收到一大堆难以理解的输出。在尝试缩小(shrink)之前，我通过使用任意实例来生成仅能产生一小组（小）值的方法来解决这个问题。为我的每个类型实现 shrink 函数似乎有所帮助，但效果不如我所愿。我仍旧会获得一大堆输出。

我认为从 shrink 中想要的是一个小型的文字列表，其中每个文字都有一个小型值列表，并且每个值列表具有少量的约束条件，每个条件都尽可能短。但是，在我目前的努力中，至少有一个这样的列表变得足够大，以致于输出变得非常可怕。如果我尝试调整我的 shrink 实现，我还发现 QC 开始花费很长时间（寻找 shrinks？），这在某种程度上抑制了我有效地缩小(shrink)的努力。

当您遇到像这样的嵌套数据时，如何提高您理解 QuickCheck 失败的机会呢？

- kowey

---

我尝试过的一些事情：更喜欢使用shrinkList shrinkNothing而不是shrinkList shrink，并且尝试使用这个替代shrinkList，它试图更倾向于删除更多元素。我怀疑我在胡闹，应该完全改变我的实现方式，或者以不同的方式进行测试 :-) - kowey

不是一个确切的答案，但你尝试过使用SmallCheck或者LazySmallCheck代替QuickCheck吗？ - Jan Christiansen

我正在考虑这个问题。我有点害怕要编写一堆新实例，但实际上并不难。我也不确定在这种列表-列表-列表的情况下是否需要这种详尽性。 - kowey

当然。这些是统一变量，例如 ?X/cat|dog ，意味着标签受限于仅与“cat”或“dog”统一（在上述简化的代码中没有标签）。除此之外，还有一个对公式进行统一的函数，以及一个扩展另一个宏数据结构（包含公式）的函数。我想检查我扩展的宏中的公式是否涵盖了原始（即模板）中的公式。 - kowey

我很震惊@ehird还没有为这个问题创建一个非常详细和有用的答案，考虑到他最近在haskell-tag问题上的活跃程度。 :) - Dan Burton

Answer 1

建议查看https://github.com/leepike/SmartCheck，它声称可以推导出比通常手动进行的更好的缩小结果。

- nh2

Answer 2

我曾经遇到过类似的问题，但是我使用的是C语言和自制的示例生成器 :) 我有一个慢而正确的实现和一个快而不正确的实现。

使用随机示例时，当您找到不正确的示例时，建议缩小示例本身。（当然，这应该由程序而不是计算机完成）

如果您有此测试的谓词，并且您有不起作用的示例，请尝试从列表中消除元素，按所有顺序（这应该是调用的线性顺序），并为每个尝试进行测试。

如果仍然失败，则没有理由保留此示例。

如果开始通过，则此元素应保留在缩小的示例中。

（这是贪婪的而不是最优的，但它在多项式时间内执行，而不是指数时间，并且对我有效）

要进行更科学的研究，我建议阅读A.Zeller的书《为什么程序失败：系统调试指南》中的“简化问题”章节。

注意：这基本上就是缩小所做的事情...

- stralep