Generating a lists of a specific length with Haskell's QuickCheck

Question

-- 3 (find k"th element of a list)
element_at xs x = xs !! x
prop_3a xs x = (x < length xs && x >= 0) ==> element_at xs (x::Int) == (xs !! x::Int)

When prop_3a is ran through QuickCheck, it gives up, because it won't generate long enough lists.

How can I write a generator that will generate lists with length longer than the random integer?

Matri

Answer 1

How about going the other way? First we let QuickCheck pick a list and then we constrain what indices we allow. This works, and does not throw away any test cases.

prop_3a (NonEmpty xs) = forAll (choose (0, length xs - 1)) $ \i ->
    element_at xs i == (xs !! i :: Int)

Here, I use forAll to use a specific generator for the indices, in this case using choose which picks an element from a specified range, and I also use the NonEmptyList type to ensure that we don't try to index into an empty list.

Beall

This seems to work perfectly, but I will need to study the code some more to understand it. :) – Matri

Other than googling, how can I find out what package provides NonEmpty? – Matri

@JoeVanDyk: It's from QuickCheck. – Beall

You can also use hoogle (haskell.org/hoogle) to observe that NonEmpty is provided by QuickCheck. – Shot

Answer 2

hammar's answer is perfectly adequate for the problem. But for the sake of answering the precise question asked, I couldn't help but investigate a bit. Let's use forAll.

prop_bang x = x >= 0 ==> forAll (listLongerThan x) $ \xs ->
  element_at xs x == xs !! x

So now we need a function, listLongerThan :: Int -> Gen [Int]. It takes a length, x, and produces a generator which will produce lists of length greater than x.

listLongerThan :: Int -> Gen [Int]
listLongerThan x = replicateM (x+1) arbitrary

It's rather straightforward: we simply take advantage of the Monad instance of Gen. If you run quickCheck prop_bang, you'll notice it starts taking quite a long time, because it begins testing absurdly long lists. Let's limit the length of the list, to make it go a bit faster. Also, right now listLongerThan only generates a list that is exactly x+1 long; let's mix that up a bit, again utilizing the Monad instance of Gen.

prop_bang =
  forAll smallNumber $ \x ->
  forAll (listLongerThan x) $ \xs ->
  element_at xs x == xs !! x

smallNumber :: Gen Int
smallNumber = fmap ((`mod` 100) . abs) arbitrary

listLongerThan :: Int -> Gen [Int]
listLongerThan x = do
  y <- fmap (+1) smallNumber -- y > 0
  replicateM (x+y) arbitrary

You can use sample smallNumber or sample (listLongerThan 3) in ghci to make sure it is generating the correct stuff.

Dafna

Instead of replicateM, I'd rather use the vector function – Langton

link to vector function: hackage.haskell.org/package/QuickCheck-2.12.6.1/docs/… – Lustihood

Answer 3

This works:

import Test.QuickCheck

element_at      :: [a] -> Int -> a
element_at xs i = xs !! i

prop_3a      :: [Int] -> Int -> Property
prop_3a xs i = (i >= 0) ==> (length xs > i) ==> element_at xs i == xs !! i

However, the problem with this is that a lot of sample values are discarded. You could use things like Positive to help with ensuring that the index is valid.

If you want to be more complex, you can use more newtype wrappers to try and generate values of sufficient length (possibly using sized, or generate the list and the index together: generate the list, and then generate the index based upon the length of the list).

Gazzo