使用 QuickCheck 生成单射函数？

Question

我正在使用 QuickCheck 生成任意函数，并且我想生成任意单射函数（即f a == f b当且仅当a == b）。

我以为我已经弄清楚了：

newtype Injective = Injective (Fun Word Char) deriving Show

instance Arbitrary Injective where
  arbitrary = fmap Injective fun
    where
      fun :: Gen (Fun Word Char)
      fun = do
        a <- arbitrary
        b <- arbitrary
        arbitrary `suchThat` \(Fn f) ->
          (f a /= f b) || (a == b)

但是我看到生成的函数将不同的输入映射到相同的输出的情况。

我想要的是：

• f使得对于所有输入a和b，要么fa不等于fb要么a等于b。

我认为我有：

• f使得存在输入a和b，其中fa不等于fb或a等于b。

我怎样才能解决这个问题？

Answer 1

您已经正确地识别了问题：您生成的是具有该属性的函数\xe2\x88\x83 a\xe2\x89\xa0b. f a\xe2\x89\xa0f b（无论如何，这对于大多数随机函数来说都是正确的），而您想要的是\xe2\x88\x80 a\xe2\x89\xa0b. f a\xe2\x89\xa0f b. 这是一个更难确保的属性，因为您需要了解生成每个单独函数值的所有其他函数值。

\n\n

我认为这不可能确保一般输入类型，但是对于单词，您可以做的是 \xe2\x80\x9cfake\xe2\x80\x9d 一个函数，通过顺序预先计算所有输出值，确保您不要重复已经完成的事情，然后只是从预定的图表中读出。它需要一点懒惰才能真正发挥作用：

\n\n

import qualified Data.Set as Set\n\nnewtype Injective = Injective ([Char] {- simply a list without duplicates -})\n deriving Show\n\ninstance Arbitrary Injective where\n  arbitrary = Injective . lazyNub <$> arbitrary\n\nlazyNub :: Ord a => [a] -> [a]\nlazyNub = go Set.empty\n where go _ [] = []\n       go forbidden (x:xs)\n        | x `Set.member` forbidden  = go forbidden xs\n        | otherwise                 = x : go (Set.insert x forbidden) xs\n

\n\n

这不是很有效，并且很可能不适合您的应用程序，但这可能是您能做的最好的事情。

\n\n

在实践中，要实际用作Injective函数，您需要将值包装在只有O (log n ) 查找时间的合适结构中。不幸的是，Data.Map.Lazy还不够懒，你可能需要手工烘焙一些东西，比如指数增长的地图列表。

\n\n

还有一个问题是，对于一些不够大的结果类型，由于没有足够的可用值，因此不可能生成单射函数。事实上，正如约瑟夫所说，这里的情况就是这样。在这种情况下，该lazyNub函数将进入无限循环。我想说，对于 QuickCheck 来说这可能没问题。

\n