haskell - 为什么这个 Hedgehog 生成器不会收缩得更快？

Question

我制作了一个 Hedgehog 生成器，它可以通过以下方式生成任意 256 位值:

genWord256 :: Gen Word256
genWord256 = do
  bytes <- Gen.integral (Range.linear 0 31)
  let lo = 2 ^ (8 * bytes)
      hi = 2 ^ (8 * (bytes + 1))
  pred <$> Gen.integral (Range.constant lo hi)

使大小参数确定数字中的字节数，我认为对我的应用程序有意义。然而，评估这个生成器如何收缩，并应用 ceiling 。 logBase 2 对此，我的问题是:

为什么 Hedgehog 决定强调其初始结果的附近？我是否以某种方式误解了“不受大小参数影响的范围”的含义？ ( Range.constant ) 我本以为这里的任何收缩都必须具有更小的位数。

λ> Gen.print genWord256
=== Outcome ===
68126922926972638
=== Shrinks ===
112                 -- 7 bits
4035711763          -- 32 bits
106639875637011     -- 47 bits
281474976710655     -- 48 bits
34204198951841647   -- 55 bits
51165560939407143   -- 56 bits
59646241933189891   -- ...
67994412286444783   -- ...
... 50 shrinks omitted ...
68126922926972637   -- 56 bits

Answer 1

您展示的输出对我来说非常有意义。

首先，为了确保我们在同一页面上，Gen.print 显示的不是一系列假设失败的相应收缩，它是只是收缩树的第一层。

因此，在您的示例中，它生成了 68126922926972638，这是一个 7 字节的值。假设失败，它将尝试 112，一个 1 字节的值。这是尽可能小的，因为它对应于第一个生成器中的值 0。如果这个测试也失败了，它将移动到收缩树的第二层，我们看不到，但可以合理地假设它将关注 1 字节值并尝试将它们收缩到 瞧。

但是，如果 112 的测试成功，它将移动到列表中的第二个值 4035711763，这是一个 4 字节值。并注意 4 个字节对应于第一个生成器中的 3，它正好在 0 和 6 之间，因为它是二进制的搜索输入的大小。如果测试再次成功，它将继续向原始结果靠拢，即“强调其初始结果的附近”，这就是我们在您的输出中看到的。