QuickCheck：产生平衡标本的嵌套数据结构的任意实例 [英] QuickCheck: Arbitrary instances of nested data structures that generate balanced specimens

问题描述

tl; dr：如何编写任意的任何的实例，如果您的数据类型允许太多嵌套，则不会爆炸？而且，您如何保证这些实例能够为您的数据结构生成真正随机的样本？

tl;dr: how do you write instances of Arbitrary that don't explode if your data type allows for way too much nesting? And how would you guarantee these instances produce truly random specimens of your data structure?

我想生成随机树结构，然后测试这些结构的某些属性使用我的图书馆代码对他们进行了调整。 （注意：我正在写一个子类型算法的实现，即给定一个类型的层次结构，类型A是类型B的子类型。通过将多重继承和初始化后更新包括在层次结构中，这可以是任意复杂的。支持这两者的经典方法是舒伯特编号，最新的结果是Alavi et al。2008。）

I want to generate random tree structures, then test certain properties of these structures after I've mangled them with my library code. (NB: I'm writing an implementation of a subtyping algorithm, i.e. given a hierarchy of types, is type A a subtype of type B. This can be made arbitrarily complex, by including multiple-inheritance and post-initialization updates to the hierarchy. The classical method that supports neither of these is Schubert Numbering, and the latest result known to me is Alavi et al. 2008.)

树，以下 Data.Tree ：

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

一个非常简单Arbitray的实例将是：

A very simple (and don't-try-this-at-home) instance of Arbitray would be:

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

由于 a 已经有$根据类型约束，c $ c>任意的实例，而 Forest 将有一个，因为 [] 也是一个例子，这似乎是直截了当的。它不会（通常）由于非常明显的原因终止：由于它生成的列表是任意长的，结构变得太大，并且很有可能不适合内存。即使是更保守的方法：

Since a already has an Arbitrary instance as per the type constraint, and the Forest will have one, because [] is an instance, too, this seems straight-forward. It won't (typically) terminate for very obvious reasons: since the lists it generates are arbitrarily long, the structures become too large, and there's a good chance they won't fit into memory. Even a more conservative approach:

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

可以调整大小参数，以保持列表的长度下降，但即使这样也不能保证终止，因为它仍然是多个连续的骰子卷，并且可能会变得非常糟糕（和我想要具有100个孩子的奇数节点。）

won't work, again, for the same reason. One could tweak the size parameter, to keep the length of the lists down, but even that won't guarantee termination, since it's still multiple consecutive dice-rolls, and it can turn out quite badly (and I want the odd node with 100 children.)

这意味着我需要限制整个树的大小。那不是那么直截了当 unordered-containers 很容易：只需使用 fromList 。这不是那么容易：你如何将一个列表随机地转变成一棵树，而不是以一种方式或另一种方式产生偏见（即不赞成左分支或非常左倾的树木）。

Which means I need to limit the size of the entire tree. That is not so straight-forward. unordered-containers has it easy: just use fromList. This is not so easy here: How do you turn a list into a tree, randomly, and without incurring bias one way or the other (i.e. not favoring left-branches, or trees that are very left-leaning.)

列表中的某种宽度优先构造（由 Data.Tree 提供的函数都是预订的）将是非常棒的，我想我可以写一个，但这样做是不平凡的。由于我现在使用树，但以后会使用更复杂的东西，我想我可能会尝试找到一个更为一般而且不那么复杂的解决方案。有没有一个，或者我将不得不诉诸写自己的非平凡的任意的生成器？在后一种情况下，我可能实际上只是采用单元测试，因为这似乎太多的工作。

Some sort of breadth-first construction (the functions provided by Data.Tree are all pre-order) from lists would be awesome, and I think I could write one, but it would turn out to be non-trivial. Since I'm using trees now, but will use even more complex stuff later on, I thought I might try to find a more general and less complex solution. Is there one, or will I have to resort to writing my own non-trivial Arbitrary generator? In the latter case, I might actually just resort to unit-tests, since this seems too much work.

推荐答案

使用 size ：

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也许这会产生过度的平衡树...

P.S. Perhaps this will generate overly balanced trees...

这篇关于QuickCheck：产生平衡标本的嵌套数据结构的任意实例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！