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

-- 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, он отказывается, потому что он не будет генерировать достаточно длинные списки.

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

Ответы

Ответ 1

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

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

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

Ответ 2

Ответ на хаммар вполне адекватен проблеме. Но, чтобы ответить на заданный вопрос, я не мог не исследовать немного. Пусть используется 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 генерала.

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, чтобы убедиться, что он генерирует правильный материал.

Ответ 3

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

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, чтобы гарантировать, что индекс действителен.

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