"Arbitrary" 的实例如何查找树？

Question

在我们的 CS 讲座中，我们目前在 Haskell 中学习了 QuickCheck。现在我的任务是使用具有以下树类型的 QuickCheck：

data Tree = Leaf Int | Node Tree Tree
  deriving (Eq, Show)

我已经写了一些必要的方程来检查树木的不同属性。我知道，我需要一个“任意”实例来运行整个事情。所以尝试了这个：

instance Arbitrary Tree where
   arbitrary = sized tree'
     where tree' 0 = do a <- arbitrary
                        oneof [return (Leaf a)]
           tree' n = do a <- arbitrary
                        oneof [return (Leaf a), return (Node (tree' (n-1)) (tree' (n-1)))]

但现在我收到一些错误，例如：

Couldn't match type `Gen Tree' with `Tree'
      Expected type: a -> Tree
        Actual type: a -> Gen Tree
    * In an equation for `arbitrary':
          arbitrary
            = sized tree'
            where
                tree' 0
                  = do a <- arbitrary
                       ....
                tree' n
                  = do a <- arbitrary
                       ....
      In the instance declaration for `Arbitrary Tree'
   |
61 |      where tree' 0 = do a <- arbitrary
   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

或：

    * Couldn't match type `Tree' with `Gen Tree'
      Expected type: Int -> Gen Tree
        Actual type: Int -> Tree
    * In the first argument of `sized', namely tree'
      In the expression: sized tree'
      In an equation for `arbitrary':
          arbitrary
            = sized tree'
            where
                tree' 0
                  = do a <- arbitrary
                       ....
                tree' n
                  = do a <- arbitrary
                       ....
   |
60 |    arbitrary = sized tree'
   |                      ^^^^^

我认为问题在于我在选择节点时进行了某种递归。因为在那种情况下，该节点的子树不是树，而更像是“return 树”。希望你明白我的意思。

有人可以帮我解决这个问题吗？

谢谢:)

Answer 1

最简单的实现方法是：

instance Arbitrary Tree where
   <b>arbitrary</b> = frequency [
       (3, Leaf <$> arbitrary)
     , (1, Node <$> <b>arbitrary</b> <*> <b>arbitrary</b>)
     ]

此处粗体显示的 arbitrary 函数是为 Tree 实例实现的函数。 Leaf 的任意项是 Int.

的 arbitrary 实例

这里我们指定任意树是任意Int的叶子，或者是任意左右子Tree的Node.

或 sized :: (Int -> Gen a) -> Gen a:

instance Arbitrary Tree where
   <b>arbitrary</b> = sized go
        where go 0 = Leaf <$> arbitrary
              go n = oneof [Leaf <$> arbitrary, Node <$> <b>go'</b> <*> <b>go'</b>]
                  where go' = go (n-1)

这里的大小指定了树的深度，而不是元素的数量。

Answer 2

这可以使用 generic-random 库

派生

{-# Language DataKinds     #-}
{-# Language DeriveGeneric #-}
{-# Language DerivingVia   #-}

import GHC.Generics
import Generic.Random.DerivingVia
import Test.QuickCheck

-- ghci> :set -XTypeApplications
-- ghci> sample @Tree arbitrary
-- Node (Leaf 0) (Node (Leaf 0) (Node (Leaf 0) (Node (Node (Leaf 0) (Leaf 0)) (Leaf 0))))
-- Leaf 0
-- Leaf (-2)
-- Leaf 5
-- Leaf 0
-- Leaf 2
-- Leaf 1
-- Leaf 7
-- Node (Leaf (-7)) (Leaf (-2))
-- Node (Leaf 4) (Node (Leaf 0) (Leaf 3))
-- Node (Leaf 5) (Leaf (-2))
data Tree = Leaf Int | Node Tree Tree
  deriving
  stock (Eq, Show, Generic)

  deriving Arbitrary
  via GenericArbitraryRec '[2, 1] Tree

如果分发有问题请告诉我！

"Arbitrary" 的实例如何查找树？

How does an instance of "Arbitrary" looks for a tree?

haskell

class

instance

quickcheck