Генерация списков определенной длины с помощью Haskell QuickCheck - PullRequest
Новая
       7

Генерация списков определенной длины с помощью Haskell QuickCheck

14 голосов
/ 08 октября 2011 
-- 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)

Когда prop_3a запускается через QuickCheck, он сдается, потому что он не будет генерировать достаточно длинные списки.

Как мне написать генератор, который будет генерировать списки, длина которых больше случайного целого числа

Ответы [ 3 ]

12 голосов
/ 08 октября 2011

ответ Хаммара вполне адекватен проблеме.Но ради ответа на поставленный точный вопрос я не мог не заняться расследованиями.Давайте использовать forAll. 

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

Так что теперь нам нужна функция, listLongerThan :: Int -> Gen [Int].Он принимает длину x и создает генератор, который создает списки длиной более x. 

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

Это довольно просто: мы просто пользуемся экземпляром Monad Gen.Если вы запустите quickCheck prop_bang, вы заметите, что это занимает довольно много времени, потому что он начинает тестировать нелепо длинные списки.Давайте ограничим длину списка, чтобы сделать его немного быстрее.Кроме того, прямо сейчас listLongerThan генерирует только список, длина которого точно равна x+1;давайте немного перепутаем, снова используя экземпляр Monad 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

Вы можете использовать sample smallNumber или sample (listLongerThan 3) в ghci, чтобы убедиться, что он генерирует правильные вещи.

10 голосов
/ 08 октября 2011

Как насчет идти другим путем?Сначала мы позволяем QuickCheck выбрать список, а затем мы ограничиваем, какие индексы мы разрешаем.Это работает и не отбрасывает никаких тестовых случаев. 

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

Здесь я использую forAll, чтобы использовать специальный генератор для индексов, в данном случае используя choose, который выбирает элемент из указанного диапазона, и я также использую тип NonEmptyList , чтобы убедиться, что мы не пытаемся индексировать в пустой список.

4 голосов
/ 08 октября 2011

Это работает: 

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

Однако проблема заключается в том, что лот выборочных значений отбрасываются.Вы можете использовать такие вещи, как Positive, чтобы убедиться, что индекс действителен.

Если вы хотите быть более сложным, вы можете использовать больше оболочек нового типа, чтобы попытаться сгенерировать значения достаточной длины (возможно, используя sized, или сгенерируйте список и индекс вместе: сгенерируйте список, а затем сгенерируйте индекс на основе длины списка).

...