Jak utworzyć dowolną instancję dla rekurencyjnego typu danych?

Question

Myślę, że tworzy to dowolne listy o długości trzeciej, ale jak utworzyć listy o dowolnej długości?

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

Z sized. To pozwala na zarządzanie wielkość generowanych arbitrary, chociaż semantyka są do instancji:

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) 

Dla porównania, tutaj jest [] „s arbitrary instance:

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

Answer 2

można użyć oneof odebrać albo pustą listę lub rekurencyjnie wygenerowania dłuższych list:

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 

Oto kilka testów:

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

---

Uwagi

jako Zeta zauważyła, że ​​ma ona oczywistą wadę choroby generowania prawdopodobnie bardzo krótkie listy:

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

jak wyciągnie Nil z prawdopodobieństwem roztworem 0,5

Zetas nie hav e ten problem!

Można dostać dostosować te prawdopodobieństwa za pomocą frequency zamiast oneof jeśli chcesz:

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

tutaj trzeba będzie p(Nil) = 0.2 i p(Cons) = 0.8 ale oczywiście można dostosować to do swoich potrzeb.

Innym sposobem jest uświadomienie sobie, że List a jest izomorficzna [a] i ponowne wystąpienie Arbitrary na listach:

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

Dzięki Zeta