使用 QuickCheck 从字符串池生成随机字符串

Question

考虑从一组可能的字符串中生成字符串的问题，以这种方式一旦选择了一个字符串，就不能再次重复。对于此任务，我想使用 QuickCheck 的 Gen 函数。

如果我看一下我尝试编写的函数的类型，它看起来很像一个状态 monad。因为我在状态 monad 中使用另一个 monad，即 Gen 。我第一次尝试使用 StateT.

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

其中：

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)

这个实现让我感到困扰的一点是我没有使用 stringGenS 的第一个元素。其次，我的最终目标是为 JSON 值定义一个随机生成器，它使用资源池（其中不仅包含字符串）。使用 StateT 使我实现了 QuickCheck 的 elements、listOf 等的 "stateful" 变体

我想知道是否有更好的方法来实现这一点，或者这种复杂性是定义现有 monad 的有状态变体所固有的。

Answer 1

StateT 和 Gen 的组合可能如下所示：

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

问题是，当您需要状态时，您不能在共享状态时运行在 Gen 中进行多次此类计算。唯一合理的做法是一起生成多个随机唯一字符串（使用相同的状态）作为

evalStateT (replicateM 10 stringGenS)

属于 GenState -> Gen [String].

类型

使用 QuickCheck 从字符串池生成随机字符串

Generating random strings from a string-pool using QuickCheck

monads

haskell

state-monad

quickcheck

monad-transformers