使用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使得for all输入a和b，或者fa不等于fb或a等于< [b。

我想我拥有的：

• f

使得存在输入a和b，其中fa不等于fb或a等于< [b。我该如何解决？

Answer 1

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

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不够懒惰，您可能需要手工烘焙一系列指数增长的地图。