使用Haskell的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)

当 prop_3a 通过 QuickCheck 运行时，它会放弃，因为它不会生成足够长的列表。

我该如何编写一个生成器以生成长度大于随机整数的列表？

- Joe Van Dyk

Answer 1

Hammar的答案对于这个问题来说是完全足够的。但是为了回答精确的问题，我不禁进行了一些调查。让我们使用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

这很简单：我们只需利用Gen的Monad实例即可。如果您运行quickCheck prop_bang，您会注意到它开始花费相当长的时间，因为它开始测试荒谬地长的列表。让我们限制列表的长度，以使其快一些。此外，现在listLongerThan仅生成恰好为x+1长的列表；让我们再次混合一下，利用Gen的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

你可以在ghci中使用sample smallNumber或sample (listLongerThan 3)来确保它生成的内容是正确的。

- Dan Burton

---

我宁愿使用vector函数，而不是使用replicateM。 - Lars Noschinski

向量函数链接：http://hackage.haskell.org/package/QuickCheck-2.12.6.1/docs/Test-QuickCheck-Arbitrary.html#v:vector - William Rusnack

Answer 2

那我们试着另外一种方式，首先让 QuickCheck 随机生成一个列表，然后再限制我们允许的索引。这种方法可行，且不会丢掉任何测试用例。

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

在这里，我使用forAll来为索引使用特定的生成器，在这种情况下使用 choose 从指定范围中选取一个元素，并且我还使用 NonEmptyList类型来确保我们不会尝试对空列表进行索引。

- hammar

---

这似乎完美地工作了，但我需要更仔细地研究代码才能理解它。 :) - Joe Van Dyk

除了谷歌搜索之外，我怎么能找到提供NonEmpty的软件包呢？ - Joe Van Dyk

@JoeVanDyk: 这来自于QuickCheck。 - hammar

你可以使用 Hoogle（http://www.haskell.org/hoogle）查看 NonEmpty 是由 QuickCheck 提供的。 - Jan Christiansen

Answer 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”的内容来确保索引有效。

如果想要更加复杂，可以使用更多的新类型包装器来尝试生成足够长度的值（可能使用“sized”），或者同时生成列表和索引：先生成列表，再根据列表长度生成索引。

- ivanm