如何爲遞歸數據類型創建任意實例？

Question

我認爲這會創建長度爲三的任意列表，但是如何創建任意長度的列表？

import Test.QuickCheck 

data List a = 
    Nil 
    | Cons a (List a) 
    deriving (Eq, Show) 

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = do 
    a <- arbitrary 
    a' <- arbitrary 
    a'' <- arbitrary 
    return $ (Cons a (Cons a' (Cons a'' (Nil)))) 

Answer 1

隨着sized。它使您能夠管理產生arbitrary的大小，雖然語義是高達實例：

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = sized go 
    where go 0 = pure Nil 
      go n = do 
      xs <- go (n - 1) 
      x <- arbitrary 
      return (Cons x xs) 

爲了便於比較，這裏是[]的arbitrary instance：

instance Arbitrary a => Arbitrary [a] where 
    arbitrary = sized $ \n -> 
    do k <- choose (0,n) 
     sequence [ arbitrary | _ <- [1..k] ] 

Answer 2

可以使用oneof挑一個空列表或遞歸產生較長的列表：

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = 
    oneof [nil, cons] 
    where nil = return Nil 
      cons = do 
      h <- arbitrary 
      tl <- arbitrary 
      return $ Cons h tl 

這裏有幾個測試：

λ> generate (arbitrary :: Gen (List Int)) 
Nil 
λ> generate (arbitrary :: Gen (List Int)) 
Cons 4 (Cons 26 Nil) 
λ> generate (arbitrary :: Gen (List Int)) 
Nil 

---

言論

爲zeta指出，這有你明顯的缺陷病產生可能非常短列表：

• P（無）= 0.5
• P（（_ Cons無）= 0.25
• P（（_ _ ConsCons無）= 0.125
• .. 。

，因爲它會繪製Nil概率0.5

齊塔溶液不甲肝這個問題！

你可以通過使用frequency代替oneof適應這些可能性，如果你喜歡：

frequency [(1,nil), (4,cons)] 

在這裏，你將有p(Nil) = 0.2和p(Cons) = 0.8當然你可以適應這個根據自己的喜好。

另一種方式是要認識到List a同構[a]和重用Arbitrary實例名單：

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = toList <$> arbitrary 

感謝澤塔