I recently ran into an issue with QuickCheck where one of my tests seemed to hang. My mistake was that I was ignoring how QuickCheck generates sized arbitrary values, and ended up creating very large structures.
Consider S-Expressions (sexps). In the following, we define a sexp as either an atom containing a string, or a list of sexps. We define an arbitrary sexp as being, with equal probability, an atom containing an arbitrary string, or a list of arbitrary sexps. Although this definition sometimes works, it may generate very deep and very big sexps.
data Sexp = List [Sexp] | Atom ByteString deriving ( Eq, Show ) instance Arbitrary Sexp where arbitrary = do n <- choose (1, 2 :: Int) case n of 1 -> Atom <$> arbitrary 2 -> List <$> arbitrary _ -> fail "can't touch this"
The issue is how QuickCheck controls the size of the generated structures. Basically, the
Gen monad, in which
arbitrary runs, passes around a size parameter, which the various
Arbitrary instances use. For instance, an arbitrary list will have a random number of elements between \(0\) and size. In our case, if you generate an arbitrary
List of at most \(100\) elements, each of which may be an arbitrary
List of at most \(100\) elements, and so on, you may generate a very big
The solution is to ensure that arbitrary sublists are smaller than their parent lists by some factor. In the following code, each sublist is at most half the size of the parent list, so the maximum depth of the top-level list is \(log_2(size)\).
instance Arbitrary Sexp where arbitrary = sized $ \sz -> do n <- choose (1, 2 :: Int) case n of 1 -> Atom <$> arbitrary 2 -> List <$> (resize (sz `div` 2) arbitrary) _ -> fail "can't touch this"