QuickCheck 中的相关收缩

Question

我面临着为一个生成器编写一个收缩函数的问题，该函数取决于另一个生成器输出的值。基本上是以下形式的生成器：

do
  a <- genA
  b <- f a
  pure $! g a b

在哪里genA :: Gen a，f :: a -> Gen b g :: a -> b -> c。为了论证的方便，假设g = (,). 那么问题是，给定一对(a, b)，收缩可能会破坏,和a之间存在的关系。afb

举个例子，请考虑以下具有缓存长度的列表：

data List =
  List
  { llength :: Int
  , list :: [Int]
  } deriving (Eq, Show)

该arbitrary函数可以很容易地定义：

instance Arbitrary List where
  arbitrary = do
    n <- choose (0, 10)
    xs <- vector n
    pure $! List { llength = n, list = xs }

然而，缩小形式的元素需要了解和List n xs之间的关系。nxs

在前面的示例中，这不是问题，因为 和 之间的关系n很xs容易确定，但是对于我正在努力确定这种关系的问题来说，这并不是微不足道的。

hedgehog像这样的集成收缩功能的库可以解决这个特定的问题（尽管并不总是如此），但是我想知道是否有一种原则性的方法可以在QuickCheck.

---

下面是一个示例，展示如何hedgehog找到列表长度小于 5 的属性的最小反例（它始终List 5 [ 0 , 0 , 0 , 0 , 0 ]作为反例给出）。这是我（认为我）目前如何解决这个问题的一个例子，基本上是通过模拟集成收缩。

hedgehog 另外，请注意，大多数时候，一元接口的行为可能不是您想要的。

Answer 1

没有灵丹妙药。据我所知，集成收缩是通用解决方案的最先进技术，并且有您提到的注意事项。它内置于 Hedgehog 中，但该方法也与 QuickCheck 100% 兼容，后者只是在缩小问题上采取中立立场，因为甚至没有接近一刀切的解决方案。

像刺猬这样具有集成收缩功能的库可以解决这个特定的问题（尽管并非总是如此），但是我想知道 QuickCheck 中是否有一种原则性的方法来解决这个问题。

这个问题表明 Hedgehog 和 QuickCheck 之间存在某种方法论上的二分法，但事实并非如此。他们遵循不同的设计理念，但一点也不反对。

集成收缩（即在同一单子中混合生成和收缩）处于通用性和便利性的最佳点；它内置于 Hedgehog 中，但也可以在 QuickCheck 之上构建等效的东西。没有根本性的障碍，只是与简单地使用 Hedgehog 中已有的内容相比，不值得付出努力。

QuickCheck 的组织方式不同，具有单独的生成器Gen a和收缩器a -> [a]。如果您想生成一棵值树并将其用于收缩（这就是集成收缩的工作原理），您可以自由地继续执行。关键是，选择是你自己做出的，而不是含蓄地为你做的；作为交换，您可以从正交概念（生成和缩小）的两个简单抽象开始，而不是通过一个将这两个概念联系在一起的更复杂的抽象。实际上，差异是表面的，并且很容易显式地分解或合并回这些抽象。