Generating random strings from a string-pool using QuickCheck

Question

Consider the problem of generating strings out our a set of possible strings, in such a way that once a string is chosen, it cannot be repeated again. For this task I would like to use QuickCheck's Gen functions.

If I look at the type of the function I'm trying to write, it looks pretty much like a state monad. Since I'm using another monad, namely Gen , inside the state monad. I wrote my first attempt using StateT.

arbitraryStringS :: StateT GenState Gen String
arbitraryStringS =
  mapStateT stringGenS get

where:

newtype GenState = St {getStrings :: [String]}
  deriving (Show)

removeString :: String -> GenState -> GenState
removeString str (St xs) = St $ delete str xs

stringGenS ::  Gen (a, GenState) -> Gen (String, GenState)
stringGenS genStSt =
  genStSt >>= \(_, st) ->
  elements (getStrings st) >>= \str ->
  return (str, removeString str st)

Something that troubles me about this implementation is the fact that I'm not using the first element of stringGenS. Secondly, my end goal is to define a random generator for JSON values, that make use of a resource pool (which contains not only strings). Using StateT led me to implement "stateful" variants of QuickCheck's elements, listOf, etc.

I was wondering whether there's a better way of achieving this, or such a complexity is inherent to defining stateful variants of existing monads.

Answer 1

The combination of StateT and Gen could look like this:

import Control.Monad.State
import Data.List (delete)
import Test.QuickCheck

-- A more efficient solution would be to use Data.Set.
-- Even better, Data.Trie and ByteStrings:
-- https://hackage.haskell.org/package/bytestring-trie-0.2.4.1/docs/Data-Trie.html
newtype GenState = St { getStrings :: [String] }
  deriving (Show)

removeString :: String -> GenState -> GenState
removeString str (St xs) = St $ delete str xs

stringGenS :: StateT GenState Gen String
stringGenS = do
  s <- get
  str <- lift $ elements (getStrings s)
  modify $ removeString str
  return str

The problem is that as you need the state, you can't run multiple such computations in Gen while sharing the state. The only reasonable thing to do would be to generate multiple random unique strings together (using the same state) as

evalStateT (replicateM 10 stringGenS)

which is of type GenState -> Gen [String].