"Arbitrary"实例如何查找树？

Question

在我们的cs讲座中，我们目前学习了Haskell中的QuickCheck。现在我有一个任务，使用QuickCheck与以下树类型:

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

我已经写了一些必要的方程来检查树的不同性质。我知道，我需要一个&;arbitrary&;的实例来管理整个项目。所以试试这个:

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'
|                      ^^^^^

我认为问题是我在选择节点时做了某种递归。因为在这种情况下，该节点的子树不是树，而更像是"返回树"。希望你明白我的意思。

有人能帮我一下吗?谢谢你:)

Answer 1

最简单的实现方法是:

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

这里arbitrary粗体显示的函数是为Tree实例实现的函数。Leaf的任意值是Int的arbitrary实例。

因此，这里我们指定任意树是具有任意Int的叶子树，或者是具有任意左右子Tree的Node树。

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

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

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

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

如果发行版有什么问题请告诉我!