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 is an example that shows how hedgehog finds the minimal counterexample for the property that the length of the list is less than 5 (it consistently gives List 5 [ 0 , 0 , 0 , 0 , 0 ] as counterexample). And here 是我（认为我）目前如何解决这个问题的一个例子，主要是通过模拟集成收缩。

此外，请注意 hedgehog is probably not what you want most of the time.

的 monadic 接口的行为

Answer 1

没有万灵药。据我所知，集成收缩是通用解决方案的最新技术，并带有您提到的警告。它内置于 Hedgehog 中，但该方法也与 QuickCheck 100% 兼容，QuickCheck 在收缩问题上只是采取中立立场，因为没有接近于一刀切的解决方案。

Libraries like hedgehog that feature integrated shrinking would solve this particular problem (albeit not always), however I'm wondering if there is a principled way to solve this in QuickCheck.

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

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

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

QuickCheck 中的相关收缩

Dependent shrinking in QuickCheck

haskell

quickcheck

haskell-hedgehog