QuickCheck sequential Map key generation

Question

I am trying to test a logic of custom data type. It receives a Map Int String as a parameter and then I need to add an element into the Map inside the object.

Type declaration and insertion function look like this:

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 }

It is important to have sequential keys in the Map, so having [0, 1, 3] is not acceptable. I was trying to test it using HSpec with 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

The problem is that QuickCheck generates random keys and I am not sure how do I force it to generate a sequential keys for the Map. The problem with absense of the sequense is that function addStr may override values in case of repetetive keys, which is not desirable behavior.

UPDATE

Thanks for all the help! After a long discussion and some kind of a thinking I ended up with the following solution:

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 $ zip [0..(length xs)] xs
            let (result, newState) = runState (create mp) state
            run(setStdGen newState)
            let result' = addStr result str
            assert $ (strsSize result) + 1 == strsSize result'

Basically, I had to generate some random set of strings and them convert in into a map manually. It is probably not the most elegant solution, but it works as needed.

When you say that QuickCheck is generating "random keys", do you mean that it is generating random StrMaps? This question is very hard for me to understand. — Rein Henrichs
This is not a minimum reproducible example so I cannot be sure, but (M.size . strs result) looks like a type error. It is very difficult to answer a question like this if your example code doesn't compile. — Rein Henrichs
It is generating a map with the content like following: {(0, "xyz"), (3, "qwerty")} or just {(5, "asd")}. In my case I need to make sure that keys always start from zero and there is no gaps between them, i.e. keys should always be 0,1,2,3,4,... — Sergii Sopin
I don't think that is what you need at all. I don't see how that is relevant to the property you are checking. You never actually test the values of the keys in any way, only the relative sizes of successive maps. — Rein Henrichs
Surely you can clarify whether it does or doesn't compile. It is your code and you can try to compile it. I was wrong about the addStr being a type error, but I have to guess about these things because your code as provided is incomplete and can't be compiled at all. — Rein Henrichs

Rein Henrichs Rein Henrichs · Accepted Answer · 2019-12-24T21:47:37

Instead of using QuickCheck to generate arbitrary data that satisfies some complex invariant, which can be difficult, you can use QuickCheck to generate fully arbitrary data from which you can then construct data that satisfies the invariant (by some method external to the system being tested which you trust to be correct).

The invariant in this case is given as "keys must be contiguous", but is actually "keys must be contiguous and start from 0". This is sufficient, but more than necessary. The minimal invariant required by addStr is "the map must not contain a key that is the size of the map", since that is the key we intend to insert. By simplifying the constraint, we also make it easier to satisfy: we can generate an arbitrary map (which may contain the bad key) and then delete the bad key, giving a satisfactory map.

I'll also note that the UUID (and thus the mechanism for generating it, which requires State and perhaps IO) is irrelevant to the property being tested. This means we can construct the MyType with any UUID we have lying around (like the nil UUID provided by the package) and avoid the monadic stuff:

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

If you wanted to, you could also make an instance of Arbitrary for MyType that does something like this, or something that satisfies the stronger invariant (which may be required for other tests). I'll leave that as an exercise for you, but feel free to ask more questions if you get stuck trying it.

QuickCheck sequential Map key generation

1 Answers