haskell - 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 的单子(monad)接口(interface)的行为is probably not what you want most of the time .

Answer 1

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

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