QuickCheck 中 Arbitrary 的唯一性和其他限制

Question

我正在尝试为我的数据类型编写修改后的 Arbitrary 实例，其中（在我的例子中）子组件的类型为 [String]。理想情况下，我希望在实例本身中带来唯一性，这样我就不需要 ==> headers / 我编写的每个测试的先决条件。

这是我的数据类型：

data Foo = Vars [String]

和琐碎的 Arbitrary 实例：

instance Arbitrary Foo where
  arbitrary = Vars <$> (:[]) <$> choose ('A','z')

这个例子很奇怪，我知道。过去，当 quickcheck 组合爆炸时，我遇到了困难，所以我想保持这些值较小。另一个请求 - 例如，我如何创建一个生成的字符串少于 4 个字符的实例？

所有这一切，从根本上需要（布尔）谓词来增加 Arbitrary 个实例。这可能吗？

Answer 1

suchThat :: Gen a -> (a -> Bool) -> Gen a 是一种在 Gen 中嵌入布尔谓词的方法。有关详细信息，请参阅 haddocks。

以下是使实例唯一的方法：

instance Arbitrary Foo where
  arbitrary = Vars <$> (:[]) <$> (:[]) <$> choose ('A','z')
              `suchThat` isUnique
    where
      isUnique x = nub x == x

Answer 2

您肯定希望实例只生成符合数据类型意图的实例。如果您希望所有变量都不同，Arbitrary 实例必须反映这一点。（另一个问题是，在这种情况下，将 Vars 定义为一个集合是否更有意义，例如 newtype Vars = Set [String]。）

我建议使用 Set 或 Hashtable 检查重复项，因为 nub 具有 O(n^2) 复杂度，对于较大的输入，这可能会大大降低您的测试速度。例如：

import Control.Applicative
import Data.List (nub)
import qualified Data.Set as Set
import Test.QuickCheck

newtype Foo = Vars [String]

-- | Checks if a given list has no duplicates in _O(n log n)_.
hasNoDups :: (Ord a) => [a] -> Bool
hasNoDups = loop Set.empty
  where
    loop _ []       = True
    loop s (x:xs) | s' <- Set.insert x s, Set.size s' > Set.size s
                    = loop s' xs
                  | otherwise
                    = False

-- | Always worth to test if we wrote `hasNoDups` properly.
prop_hasNoDups :: [Int] -> Property
prop_hasNoDups xs = hasNoDups xs === (nub xs == xs)

然后您的实例需要创建一个列表列表，每个列表应该是随机的。因此，您需要调用 listOf 两次，而不是 (: [])，它只创建一个单例列表（并且只有一个级别）：

instance Arbitrary Foo where
  arbitrary = Vars <$> (listOf . listOf $ choose ('A','z'))
                       `suchThat` hasNoDups

还要注意 choose ('A', 'z') 允许使用 A 和 z 之间的所有字符，其中包括许多控制字符。我的猜测是你更想要像

这样的东西

oneof [choose ('A','Z'), choose ('a','z')]

如果你真的想要，你也可以使用 hash tables in the ST monad 使 hasNoDups O(n)。

关于限制大小：您总是可以拥有自己的参数化函数来产生不同的 Gen Foo，但我想说在大多数情况下没有必要。 Gen 有它自己的内部大小参数，该参数在整个测试过程中都会增加（请参阅 this answer），因此涵盖了不同大小（使用 listOf 生成）的列表。

但我建议你实施 shrink，因为这会给你更好的反例。例如，如果我们定义（一个错误的测试）试图验证 Var 的任何实例在其任何变量中都不包含 'a'：

prop_Foo_hasNoDups :: Foo -> Property
prop_Foo_hasNoDups (Vars xs) = all (notElem 'a') xs === True

我们会得到丑陋的反例，例如

Vars ["RhdaJytDWKm","FHHhrqbI","JVPKGTqNCN","awa","DABsOGNRYz","Wshubp","Iab","pl"]

但添加

shrink (Vars xs) = map Vars $ shrink xs

到Arbitrary Foo使得反例只是

Vars ["a"]

QuickCheck 中 Arbitrary 的唯一性和其他限制

Uniqueness and other restrictions for Arbitrary in QuickCheck

haskell

predicate

unique

quickcheck