使用 Arbitrary 类型类生成随机二叉搜索树

Question

我正在处理一个问题集，我必须为二叉搜索树编写一个任意实例。这是我到目前为止编写的代码：

data Tree e = E | N (Tree e) e (Tree e)

insert :: (Ord e) => e -> Tree e -> Tree e
-- assume this is implemented, so I can use it below

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where
    arbitrary :: Gen (Tree a)
    arbitrary = sized gen
      where
        gen :: Int -> Gen a
        gen n =
          frequency
            [
              (1, return E),
--                         vvvvvvvvv problematic vvvvvvvvvv
              (n, return $ insert (4::Int) (gen (n `div` 2)))
            ]

我不确定如何让频率列表的第二行进行类型检查。我可以看到 gen returns a Gen Tree and insert requires a Tree for its second argument，但我不确定如何用它重构代码知识。但是，我需要使用 insert 函数。另一个问题是我需要获取随机元素值，但我暂时把它放在一边，让每个新元素成为 4 :: Int.

Answer 1

gen (n `div` 2) 的类型是 Gen (Tree a)，所以你应该 fmap 那棵树，所以：

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where
    arbitrary = sized gen
      where gen n = frequency [
                (1, return E)
              , (n, <strong>insert <$> arbitrary <*> gen (n `div` 2)</strong>)
              ]

这将因此生成一个 arbitrary 值，然后是大小为 n `div` 2 的任意 Tree，然后 return insert 的结果该任意子树的任意值。

使用 Arbitrary 类型类生成随机二叉搜索树

Generating random binary search trees with the Arbitrary typeclass

haskell

random

binary-search-tree

quickcheck

arbitrary-values