使用 QuickCheck 生成单射函数？

Question

我正在使用 QuickCheck 生成任意函数，我想生成任意 injective 函数（即 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，或者 f a 不等于 f b 或者 a 等于 b .

我认为我拥有的：

f 这样存在输入 a 和 b 其中 f a 不等于 f b 或 a 等于 b .

我该如何解决这个问题？

Answer 1

您已经正确地识别了问题：您生成的是带有属性 ∃ a≠b. f a≠f b 的函数（这对大多数随机函数来说都是正确的），而您想要的是 ∀ a≠b. f a≠f b。属性要确保这一点要困难得多，因为您需要了解所有其他函数值才能生成每个单独的函数值。

我认为这对于一般输入类型来说是不可能的，但是对于单词，你可以做的是通过顺序预先计算所有输出值来“伪造”一个函数，确保你不会重复一个已经完成的，然后只是从该预定图表中读取。它需要一点懒惰才能真正让这个工作：

import qualified Data.Set as Set

newtype Injective = Injective ([Char] {- simply a list without duplicates -})
 deriving Show

instance Arbitrary Injective where
  arbitrary = Injective . lazyNub <$> arbitrary

lazyNub :: Ord a => [a] -> [a]
lazyNub = go Set.empty
 where go _ [] = []
       go forbidden (x:xs)
        | x `Set.member` forbidden  = go forbidden xs
        | otherwise                 = x : go (Set.insert x forbidden) xs

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

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

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

使用 QuickCheck 生成单射函数？

Generate injective functions with QuickCheck?

testing

haskell

functional-programming

quickcheck