使用 Arbitrary 类型类生成随机二叉搜索树
我正在研究一个问题集，我必须为二叉搜索树编写任意实例。这是我到目前为止编写的代码：
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 返回一个 Gen Tree 并且 insert 需要一个 Tree 作为它的第二个参数，但我不确定如何利用这些知识重组代码。但是，我需要使用 insert 函数。另一个问题是我需要获取随机元素值，但我暂时将其放在一边，并将每个新元素设置为 4 :: Int。
I am working on a problem set where I must write an arbitrary instance for binary search trees. Here is the code I've written so far:
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)))
]
I'm unsure of how to get the second line of the frequency list to type check. I can see gen returns a Gen Tree and insert requires a Tree for its second argument, but I'm not sure how to restructure the code with that knowledge. It is required I use the insert function, however. Another problem is I need to get random element values, but I've put that aside for now and made every new element a 4 :: Int.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
gen (n `div` 2)的类型为Gen (Tree a)，因此您应该fmap该树，因此：这将生成一个
任意值，然后是一个大小为n `div` 2的任意Tree，然后返回插入的结果code> 具有该任意子树的任意值。gen (n `div` 2)has typeGen (Tree a), so you shouldfmapthat tree, so:This will thus generate an
arbitraryvalue, then an arbitraryTreewith sizen `div` 2, and then return the result of aninsertwith that arbitrary value for that arbitrary subtree.