Quickcheck: produce arbitrary elements of an arbitrary set

Question

Suppose that I am writing tests for Data.Set. I would like to check that deleting elements from the set works, and so I might write something like this:

prop_deleteA it x = member x it ==> not (member x (delete x it))

assuming that it has a suitable Arbitrary instance. However, this relies on quickcheck generating values of x that happen to exist within the set, which is not in general guaranteed. It would be much better if x could be made to depend on it so as to guarantee that x is already a member of it. How might I do this?

I had the thought that I could write

prop_deleteB it f = let x = f it
                   in not (member x (delete x it))

where f :: Set a -> a is suitably defined by means of coarbitrary. However, coarbitrary would only allow us to define f :: Set a -> b, which unfortunately isn't what we want. My best thought so far has been to define a new type

data SetAndElement a = SetAndElement (Set a) a

which allows us to write a suitable Arbitrary instance

instance (Ord a, Arbitrary a) => Arbitrary (SetAndElement a) where
    arbitrary = do it <- suchThat arbitrary (not . Set.null)
                   x  <- elements (elems it)
                   return (SetAndElement it x)

allowing prop_delete to be written as

prop_deleteC (SetAndElement it x) = not (member x (delete x it))

This works, but seems a little involved; are there any better options? (If not, I'll modify the question and put this as an answer.) The actual Data.Set implementation (containers package) tests deletion by checking that (delete x) . (insert x) == id if x was not already a member of the given set.

Answer 1

It depends on what generators you have available. For example, if you already have setOf1 (generates a Set with at least one element) and setElements (takes elements from a Set), it can be written with forAll:

-- example implementations of both combinators
setOf1 :: (Arbitrary a, Ord a) => Gen a -> Gen (Set a)
setOf1 = fmap fromList . listOf1

setElements :: Set a -> Gen a
setElements = elements . toList

prop_delete =
  forAll (setOf1 arbitrary)   $ \theSet ->
  forAll (setElements theSet) $ \x ->
    not (member (x :: Int) (delete x theSet))

This is mostly the same as SetAndElement, but instead of a fixed data type, we're using re-usable functions that can be used for further tests:

prop_null =  forAll (setOf1 (arbitrary :: Gen Integer)) $ not . null

However, even if you don't write setOf1 or setElements, forAll can be rather succinct for simple tests:

prop_delete :: (Arbitrary a, Ord a) => (NonEmptyList a) -> Property
prop_delete (NonEmpty xs) =
  let theSet = fromList xs
  in forAll (elements xs) $ \x ->
      not (member x (delete x theSet))

If you provide setElements and NonEmptySet, this can be written as

newtype NonEmptySet x = NonEmptySet {getNonEmptySet :: Set a}

instance (Ord a, Arbitray a) => Arbitrary (NonEmptySet a) where
  arbitrary = fmap NonEmptySet . setOf1 $ arbitrary

prop_delete :: (Arbitrary a, Ord a) => (NonEmptySet a) -> Property
prop_delete (NonEmptySet theSet) =
  forAll (setElements theSet) $ \x ->
    not (member x (delete x theSet))

That way you can use NonEmptySet for tests that require a non-empty set, and setElements only for those where you actually need to choose an element at random.