快速检查：产生均衡的标本嵌套数据结构的任意实例(QuickCheck: Arbitrary inst

TL;博士：你怎么写的情况下， Arbitrary如果您的数据类型允许太多的嵌套不爆炸？而你将如何保证这种情况下产生的数据结构的真正的随机样本？

我想随机生成的树结构，然后测试这些结构我已经错位他们与我的库代码之后的某些属性。（注：我在写一个分型算法的实现，即给定的类型层次结构，类型是B型的一个亚型这可以任意复杂，通过包括多重继承和初始化后更新的层次。支持这些都不是舒伯特编号已知我的经典方法，以及最新的结果是阿拉维等人。2008年）

让我们的玫瑰树，下面的例子Data.Tree ：

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

一个非常简单的（和鸵鸟政策尝试，这在家里）任意波形的实例是：

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

（改编自所述快速检查介绍）。

PS也许这会产生过度平衡树...

Answer 2:

您可能需要使用的文件中提出的图书馆“的壮举：代数类型的功能枚举”在哈斯克尔研讨会2012年正是在Hackage作为测试-壮举，而谈话的引入它的视频，请访问： HTTP：/ /www.youtube.com/watch?v=HbX7pxYXsHg

Answer 3:

正如詹尼斯提到的，你可以使用包测试-壮举，创造任意代数数据类型的枚举。这是创造最多给定大小的所有树木公正的均匀分布生成最简单的方法。

这里是你将如何使用它的玫瑰树：

import Test.Feat (Enumerable(..), uniform, consts, funcurry)
import Test.Feat.Class (Constructor)
import Data.Tree (Tree(..))
import qualified Test.QuickCheck as QC

-- We make an enumerable instance by listing all constructors
-- for the type. In this case, we have one binary constructor:
-- Node :: a -> [Tree a] -> Tree a
instance Enumerable a => Enumerable (Tree a) where
    enumerate = consts [binary Node]
      where
        binary :: (a -> b -> c) -> Constructor c
        binary = unary . funcurry

-- Now we use the Enumerable instance to create an Arbitrary
-- instance with the help of the function:
-- uniform :: Enumerable a => Int -> QC.Gen a
instance Enumerable a => QC.Arbitrary (Tree a) where
    QC.arbitrary = QC.sized uniform
    -- QC.shrink = <some implementation>

该Enumerable也可以与TemplateHaskell自动生成的实例：