为什么这个 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)

让 size 参数决定数字中的字节数，我认为对我的应用程序很有意义。但是，评估此生成器如何缩小并应用于ceiling . logBase 2此，我的问题是：

为什么刺猬决定强调其初始结果的附近？我是否以某种方式误解了“不受大小参数影响的范围”的含义？( 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 字节值并尝试将它们收缩到 是合理的lo。

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