我正在研究一個問題集，我必須為二叉搜索樹撰寫任意實體。這是我到目前為止撰寫的代碼：
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回傳 aGen Tree并且insert需要 aTree作為其第二個引數，但我不確定如何使用該知識重構代碼。但是，我需要使用該insert功能。另一個問題是我需要獲取隨機元素值，但我暫時將其放在一邊，并將每個新元素都設為4 :: Int.
uj5u.com熱心網友回復：
gen (n `div` 2)有 type Gen (Tree a)，所以你應該fmap那棵樹，所以：
instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where
arbitrary = sized gen
where gen n = frequency [
(1, return E)
, (n, insert <$> arbitrary <*> gen (n `div` 2))
]因此，這將生成一個arbitrary值，然后是任意Tree大小的任意值，n `div` 2然后回傳insert任意子樹的任意值的結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/437993.html