QuickCheck顺序映射密钥生成

Question

我正在尝试测试自定义数据类型的逻辑。它接收Map Int String作为参数，然后我需要在对象内部的Map中添加一个元素。

类型声明和插入函数如下：

import qualified Data.IntMap.Strict as M
import Data.UUID (UUID)
import Control.Monad.State
import System.Random

type StrMap = M.IntMap String
type MType = State StdGen

data MyType = MyType {
    uuid :: UUID,
    strs :: StrMap
} deriving (Show)

create :: StrMap -> MType MyType
create pm = do
    state <- get
    let (uuid, newState) = random state
    put newState
    return $ MyType uuid pm

strsSize :: MyType -> Int
strsSize e = M.size $ strs e

addStr :: MyType -> String -> MyType
addStr e p = e { strs = M.insert (strsSize e) p $ strs e }

在Map中具有顺序键很重要，因此具有[0，1，3]是不可接受的。我试图通过HSpec和QuickCheck对其进行测试：

main :: IO ()
main = hspec spec

spec :: Spec
spec = describe "Creation and update" $ do
    QuickCheck.prop "Check map addition" $ do
        \xs str -> monadicIO $ do
            state <- run(getStdGen)
            let (result, newState) = runState (create xs) state
            run(setStdGen newState)
            let result' = addStr result str
            assert $ (strsSize result) + 1 == strsSize result' -- fails here

问题是QuickCheck会生成随机密钥，我不确定如何强制它为Map生成顺序密钥。缺少序列的问题是，在重复键的情况下，函数addStr可能会覆盖值，这是不希望的行为。

---

UPDATE

感谢所有帮助！经过长时间的讨论和某种思考，我得出了以下解决方案：

spec :: Spec
spec = describe "Creation and update" $ do
    QuickCheck.prop "Check map addition" $ do
        \xs str -> not (null xs) Property.==> monadicIO $ do
            state <- run(getStdGen)
            let mp = M.fromList [(a,b) | a <- [0..(length xs)], b <- xs]
            let (result, newState) = runState (create mp) state
            run(setStdGen newState)
            let result' = addStr result str
            assert $ (strsSize result) + 1 == strsSize result'

[基本上，我必须生成一些随机的字符串，然后将它们手动转换为映射。它可能不是最优雅的解决方案，但可以根据需要运行。

Answer 1

而不是使用QuickCheck来生成满足某些复杂不变性的任意数据，这可能很困难，您可以使用QuickCheck生成完全任意的数据，然后可以从中构建满足不变性的数据（通过外部的某种方法您认为正确的被测系统）。

在这种情况下，不变式为“键必须是连续的”，但实际上是“键必须是连续的并从0开始”。这是足够的，但超出了必要。 addStr所要求的最小不变性是“映射不得包含映射大小的键”，因为这是我们打算插入的键。通过简化约束，我们还可以更轻松地满足要求：我们可以生成一个任意映射（可能包含坏键），然后删除该坏键，从而得到令人满意的图。

我还将注意到，UUID（以及生成UUID的机制，需要State甚至可能是IO）与要测试的属性无关。这意味着我们可以使用我们随身携带的任何MyType来构造UUID（如程序包提供的nil UUID），并避免使用单子代码：

spec :: Spec
spec = describe "Creation and update" $ do
  QuickCheck.prop "Check map addition" $ do
    \strmap -> -- we don't actually care what the String being inserted is for this test
      let myType = MyType UUID.nil (M.delete (M.size strmap) strmap) -- Enforce the invariant
      in assert $ strsSize (addStr myType "") = strsSize myType + 1

[如果需要，您也可以为Arbitrary创建一个MyType的实例，该实例执行类似的操作，或者满足更强不变性的条件（其他测试可能需要）。我会将其留给您练习，但是如果您坚持尝试，可以随时提出更多问题。