How do I create an arbitrary instance for a recursive datatype?

Question

I think this creates arbitrary lists of length three, but how do I 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 enables you to manage the size of the generated arbitrary, although the semantics are up to the instance:

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 is []'s 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 pick 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 a few 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 pointed out this has the obvious flaw that you will generate probably very short lists:

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

as it will draw Nil with probability 0.5

Zetas solution does not have this problem!

You can get adapt these probability by using frequency instead of oneof if you like:

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 realize that List a is isomorphic to [a] and reuse the Arbitrary instance for lists:

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

Thanks Zeta