How to fix ambiguity of an Arbitrary instance of a list-like type

Question

Consider the following:

import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes

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

instance Functor List where
    fmap _ Nil = Nil
    fmap f (Cons a l) = Cons (f a) (fmap f l)

instance Eq a => EqProp (List a) where (=-=) = eq

genList :: Arbitrary a => Gen (List a)
genList = do
    n <- choose (3 :: Int, 5)
    gen <- arbitrary
    elems <- vectorOf n gen
    return $ build elems
  where build [] = Nil
        build (e:es) = Cons e (build es)

instance Arbitrary a => Arbitrary (List a) where
    arbitrary = frequency [ (1, return Nil)
                          , (3, genList)
                          ]

main = quickBatch $ functor (Nil :: List (Int, String, Int))

This doesn't compile because of the ambiguity in genList:

• Could not deduce (Arbitrary (Gen a))
    arising from a use of ‘arbitrary’
  from the context: Arbitrary a
    bound by the type signature for:
               genList :: forall a. Arbitrary a => Gen (List a)
    at reproducer.hs:13:1-38
• In a stmt of a 'do' block: gen <- arbitrary
  In the expression:
    do n <- choose (3 :: Int, 5)
       gen <- arbitrary
       elems <- vectorOf n gen
       return $ build elems
  In an equation for ‘genList’:
      genList
        = do n <- choose (3 :: Int, 5)
             gen <- arbitrary
             elems <- vectorOf n gen
             ....
        where
            build [] = Nil
            build (e : es) = Cons e (build es)
   |
16 |     gen <- arbitrary
   |            ^^^^^^^^^

I know that I can write genList as genList = Cons <$> arbitrary <*> arbitrary, but I would like to know. How do I remove the ambiguity? Isn't the type assertion in main supposed to clear it?

Answer 1

vectorOf expects a Gen a. Therefore, GHC tries to find an instance of Arbitrary for Gen a, which doesn't exist.

Use vectorOf n arbitrary or just vector n. Also, it's recommended to use sized to have QuickCheck choose the size:

genList :: Arbitrary a => Gen (List a)
genList = sized $ \n ->
    elems <- vector n
    return $ build elems
  where build [] = Nil
        build (e:es) = Cons e (build es)

However, at that point we're already better of using listOf instead:

genList :: Arbitrary a => Gen (List a)
genList = build <$> listOf arbitary
  where build = foldr Cons Nil

Note that genList = Cons <$> arbitrary <*> arbitrary won't generate empty lists, whereas foldr Cons Nil <$> listOf arbitrary will.