28

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

我想生成随机树结构，然后在我用我的库代码破坏它们之后测试这些结构的某些属性。（注意：我正在编写子类型算法的实现，即给定类型的层次结构，类型 A 是类型 B 的子类型。这可以任意复杂化，包括对层次结构的多重继承和初始化后更新. 不支持这两种方法的经典方法是舒伯特编号，我知道的最新结果是 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已经有一个实例，并且将有一个，因为它也是一个实例，这看起来很简单。它不会（通常）由于非常明显的原因而终止：由于它生成的列表任意长，结构变得太大，并且它们很可能不适合内存。甚至更保守的方法：ArbitraryForest[]

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

出于同样的原因，再次无法正常工作。可以调整 size 参数，以降低列表的长度，但即使这样也不能保证终止，因为它仍然是多个连续的掷骰子，结果可能非常糟糕（我想要奇数节点 100孩子们。）

这意味着我需要限制整个树的大小。这不是那么直截了当。unordered-containers很简单：只需使用fromList. 这在这里并不容易：如何将列表随机变成一棵树，并且不会以某种方式产生偏见（即不支持左分支或非常左倾的树。）

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

4

3 回答 3

21

使用尺寸：

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

于 2013-04-11T22:20:29.403 回答
7

您可能想使用在 Haskell Symposium 2012 上发表的论文“Feat:Functional Enumeration of Algebraic Types”中介绍的库。它在 Hackage 上作为 testing-feat，介绍它的演讲视频可在此处获得：http:// /www.youtube.com/watch?v=HbX7pxYXsHg

于 2013-05-02T10:51:27.520 回答
2

正如 Janis 所提到的，您可以使用包testing-feat，它创建任意代数数据类型的枚举。这是为给定大小的所有树创建无偏均匀分布生成器的最简单方法。

以下是您将它用于玫瑰树的方法：

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 自动生成：

deriveEnumerable ''Tree
于 2018-04-10T13:11:37.643 回答