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

Question

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

我想生成随机树结构,然后在用我的库代码修改它们之后测试这些结构的某些属性.(注意:我正在编写子类型算法的实现,即给定类型的层次结构,类型A是类型B的子类型.通过在层次结构中包含多继承和后初始化更新,可以使其任意复杂化不支持这些的经典方法是Schubert编号,我所知道的最新结果是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个)孩子们.)

这意味着我需要限制整个树的大小.那不是那么直截了当.unordered-containers很简单:只需使用fromList.这在这里不是那么容易:你如何随机地将一个列表变成一棵树,而不会产生任何一种或另一种偏见(即不利于左分支,或者是非常左倾的树.)

列表中的某种广度优先构造(Data.Tree所有预先提供的功能)都很棒,我想我可以写一个,但结果却是非平凡的.由于我现在正在使用树,但是后来会使用更复杂的东西,我想我可能会尝试找到更通用,更简单的解决方案.有没有,还是我不得不求助于编写我自己的非平凡Arbitrary发电机？在后一种情况下,我实际上可能只是采用单元测试,因为这似乎太多了.

Answer 1

使用大小:

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

(改编自QuickCheck演示文稿).

PS也许这会产生过于平衡的树木......

Answer 2

您可能希望使用Haskell Symposium 2012中的文章"Feat:Functional Enumeration of Algebraic Types"中提供的库.它在Hackage上作为测试专长,并且可以在此处获得介绍它的视频:http:/ /www.youtube.com/watch?v=HbX7pxYXsHg