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可能会破坏a，f和b之间存在的关系。

作为示例，请考虑以下列表，该列表具有缓存的长度：

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形式的元素需要n和xs之间的关系的一些知识。

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

hedgehog之类的具有集成收缩功能的库将解决此特定问题（尽管not always，但是我想知道QuickCheck中是否存在解决这一问题的原则方法。

---

Here是一个示例，显示hedgehog如何查找列表长度小于5的属性的最小反例（它始终以List 5 [ 0 , 0 , 0 , 0 , 0 ]作为反例）。 here是一个示例，说明了我（认为我）目前基本上是通过模拟集成收缩来解决此问题的方法。

此外，请注意hedgehog is probably not what you want most of the time的单子界面的行为。

Answer 1

没有万能药。据我所知，集成收缩是通用解决方案的最新技术，并带有您提到的警告。它内置在Hedgehog中，但是该方法也与QuickCheck 100％兼容，QuickCheck仅在缩小问题上采取中立立场，因为甚至没有一种方法可以解决所有问题。

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

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

整体收缩（即在同一单子单元中混合生成和收缩）处于普遍性和便利性的最佳点；它内置在Hedgehog中，但也可以在QuickCheck的基础上构建等效的东西。没有根本的障碍，与仅使用刺猬中已有的东西相比，这是不值得的努力。

QuickCheck的组织方式不同，具有单独的生成器Gen a和收缩器a -> [a]。如果要生成值树并将其用于收缩（集成收缩是这样工作的），则可以随意进行。关键是，选择权由您自己决定，而不是隐含地为您做出。作为交换，您将开始使用两个简单的正交概念抽象（生成和收缩），而不是将两个概念捆绑在一起的更复杂的抽象。实用上，差异是肤浅的，并且很容易将这些抽象明确地分解或合并。