How to create an arbitrary instance for a recursive data type?

Question

I think this creates arbitrary lists of length three, but how to create lists of arbitrary length?

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

With sized . It allows you to control the size of the generated arbitrary , although the semantics are instance dependent:

 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) 

For comparison, here [] an arbitrary instance :

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

Answer 2

you can use oneof to select either an empty list or recursively generate longer lists:

 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 

here are some tests:

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

---

remarks

As zeta has shown, this has an obvious flaw that you will create, probably very short lists:

• p (Nil) = 0.5
• p ((_ Cons Nil) = 0.25
• p ((_ Cons _ Cons Nil) = 0.125
• ...

how he draws Nil with a probability of 0.5

Zetas solution does not have this problem!

You can adapt this probability using frequency instead of oneof if you want:

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

here you will have p(Nil) = 0.2 and p(Cons) = 0.8 , but of course you can adapt this to your liking.

Another way is to understand that List a is isomorphic [a] and reuse an Arbitrary instance for lists:

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

Thank you Zeta strong>