Yinelemeli veri türü için nasıl rasgele bir örnek oluştururum?

Question

Bunun üçüncüsü rasgele listeler oluşturduğunu düşünüyorum, ancak nasıl rasgele uzunluk listeleri oluşturabilirim?

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

. Karşılaştırma için

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) 

burada, [] 'ın arbitrary instance geçerli:: Bu semantik örneğine kadar olmasına rağmen, arbitrary oluşturulan boyutunu yönetmenize olanak tanır

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

Answer 2

daha uzun listeleri boş bir liste ya almak veya ters üretmek için oneof kullanabilirsiniz:

olarak

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

---

açıklamalar: Burada

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 

birkaç testlerdir zeta, bunun açık bir kusura sahip olduğuna işaret etti. hasta muhtemelen çok kısa listeleri oluşturabilir:

• p (Nil) = 0,5
• p ((_ Cons Nil) = 0,25
• p ((_ Cons _ Cons Nil) = 0,125
• .. .

0,5

Zeta da çözelti hav etmez bu olasılık ile Nil çekecek şekilde e bu problem! İstersen

Sen frequency kullanarak yerine oneof bu olasılık adapte alabilirsiniz: Burada

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

Eğer p(Nil) = 0.2 ve p(Cons) = 0.8 olacak ama tabii ki sizin beğeninize bu uyum sağlayabilir.

bir başka yolu listeler için Arbitrary örneği List a[a] izomorf olduğunu fark ve yeniden geçerli: sized ile

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

Teşekkür Zeta