testing - QuickCheck:生成平衡样本的嵌套数据结构的任意实例

Question

tl;dr:如果您的数据类型允许太多嵌套，您如何编写不会爆炸的 Arbitrary 实例？您如何保证这些实例产生您的数据结构的真正随机样本？

我想生成随机树结构，然后在用我的库代码破坏这些结构后测试它们的某些属性。 (注意:我正在编写一个子类型化算法的实现，即给定一个类型层次结构，类型 A 是类型 B 的子类型。这可以通过包含多重继承和初始化后更新到层次结构而变得任意复杂. 不支持这两个的经典方法是Schubert Numbering，我知道的最新结果是Alavi et al. 2008。)

让我们以玫瑰树为例，遵循 Data.Tree:

data Tree a = Node a (Forest a)
type Forest a = [Tree a]

Arbitray 的一个非常简单(不要在家尝试)的实例是:

instance (Arbitrary a) => Arbitrary (Tree a) where
    arbitrary = Node <$> arbitrary <$> arbitrary

因为 a 已经有一个 Arbitrary 实例，根据类型约束，Forest 将有一个，因为 [] 也是一个实例，这看起来很简单。它不会(通常)因非常明显的原因而终止:由于它生成的列表任意长，结构变得太大，并且它们很可能无法放入内存。更保守的方法:

arbitrary = Node <$> arbitrary <*> oneof [arbitrary,return []]

出于同样的原因，再次不起作用。可以调整大小参数，以减少列表的长度，但即使这样也不能保证终止，因为它仍然是多次连续的掷骰子，而且结果可能很糟糕(而且我想要有 100 个 child 的奇数节点。)

这意味着我需要限制整棵树的大小。这不是那么简单。 unordered-containers 很简单:只需使用 fromList。这在这里并不那么容易:如何随机地将列表变成一棵树，并且不会以任何方式产生偏见(即不偏向左分支或非常左倾的树。)

列表中的某种广度优先构造(Data.Tree 提供的函数都是预先排序的)会很棒，我想我可以写一个，但结果会是不平凡的。由于我现在正在使用树，但以后会使用更复杂的东西，我想我可能会尝试找到一个更通用、更简单的解决方案。有没有一个，或者我将不得不诉诸于编写我自己的非平凡 Arbitrary 生成器？在后一种情况下，我实际上可能只是求助于单元测试，因为这看起来工作量太大。

Answer 1

使用sized :

instance Arbitrary a => Arbitrary (Tree a) where
arbitrary = sized arbTree

arbTree :: Arbitrary a => Int -> Gen (Tree a)
arbTree 0 = do
    a <- arbitrary
    return $ Node a []
arbTree n = do
    (Positive m) <- arbitrary
    let n' = n `div` (m + 1)
    f <- replicateM m (arbTree n')
    a <- arbitrary
    return $ Node a f

(改编自 the QuickCheck presentation )。

附言也许这会生成过度平衡的树...