4

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

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 ]作为反例给出）。这是我（我认为我）目前如何解决这个问题的一个例子，基本上是通过模拟集成收缩。

另外，请注意，monadic 接口的行为在hedgehog 大多数情况下可能不是您想要的。

4

1 回答 1

3

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

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

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

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

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

于 2019-12-24T14:20:04.460 回答