为什么 `fst (Random.split gen)` 返回的生成器有时会产生与 `gen` 相同的结果？

Question

我正在尝试创建列表的随机排列。我是函数式语言中随机性的新手，还没有完全掌握 monad，但我已经以我认为应该有效的方式使用了 Random.newStdGen 和 Random.Shuffle.shuffle'。

我运行遇到的问题是，我得到了很多重复的排列，以至于我似乎错误地使用或错误地理解了生成器的拆分函数。

相关函数在这里：

doGenerateInput :: [[Int]] -> System.Random.StdGen -> Int -> Int -> [[Int]]
doGenerateInput acc gen n 0 = acc
doGenerateInput acc gen n k =
  doGenerateInput
    (System.Random.Shuffle.shuffle' [1 .. n] n gen : acc) accumulator
    (fst (System.Random.split gen))
    n
    (k -1)

generateInput :: Int -> Int -> IO [[Int]]
generateInput n k = do
  gen <- System.Random.newStdGen
  return (doGenerateInput [] gen n k)

这里 generateInput 应该创建 k [1..n] 的随机排列。它在将生成器传递到下一级递归之前将其拆分，因此每个排列在统计上应该彼此无关。然而，我得到的实际结果包括大量重复项。通常连续两次返回相同的排列。有时甚至连续三次。有人对我可能做错的地方有什么建议吗？

这是我从中收到的输出。

8 18 1 6 17 19 7 9 15 2 11 12 20 16 10 5 4 14 13 3
12 11 8 20 1 6 19 7 9 17 2 13 14 18 10 5 4 16 15 3
3 13 12 9 1 2 8 10 11 19 4 15 16 20 14 7 6 18 17 5
3 13 12 9 1 2 8 10 11 19 4 15 16 20 14 7 6 18 17 5
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
8 6 9 10 7 11 3 19 18 20 15 1 2 14 17 16 4 12 5 13
18 8 6 9 10 7 11 3 20 19 15 1 2 14 17 16 4 12 5 13
8 11 5 13 15 4 20 18 16 14 10 3 12 1 19 7 9 6 2 17
16 8 11 5 13 6 15 18 4 19 17 12 3 14 1 9 10 7 2 20
2 17 9 12 6 14 7 16 19 5 20 18 13 4 15 1 8 11 3 10
7 2 18 10 6 14 8 16 9 19 5 20 15 4 17 1 11 13 3 12
17 7 2 19 13 10 6 15 8 18 9 5 14 11 16 3 1 20 4 12
11 4 19 8 2 6 16 13 9 18 10 12 20 3 7 15 5 1 17 14
17 11 4 20 13 10 8 2 6 19 15 9 3 14 5 18 16 7 1 12
17 11 4 20 13 10 8 2 6 19 15 9 3 14 5 18 16 7 1 12
12 18 11 4 1 15 13 9 3 7 17 10 5 16 6 20 19 8 2 14
12 18 11 4 1 15 13 9 3 7 17 10 5 16 6 20 19 8 2 14

根据 split 的文档，我希望从 split 返回的两个生成器不相关。但是重复率似乎表明用 fst (split gen) 生成随机数产生的结果与 gen 大约一半的时间相同。

Returns two distinct pseudo-random number generators. Implementations should take care to ensure that the resulting generators are not correlated.

https://hackage.haskell.org/package/random-1.2.1/docs/System-Random.html#v:split

我找到了解决办法，但我不明白为什么会这样

如果我使用 snd (split gen) 而不是 fst (split gen)，我不会得到任何重复。但是根据文档，我不确定为什么。它没有记录返回的第一个和第二个生成器之间的区别。

如有任何见解，我们将不胜感激。

Answer 1

在 random 的设计中有一些假设，即 RandomGen 值仅使用一次。当您重复使用它们时，可能会发生奇怪的事情。我不知道 RandomGen 的 split 是如何实施来给你这个结果的，但我可以告诉你，这是假设你不会做你正在做的事情。将 gen 传递给 split 和 shuffle' 是使用它两次。为您的用例使用 split 的预期方法是预先调用 split，然后将其 return 值之一传递给 shuffle'，另一个传递给递归调用。

Answer 2

您不需要使用 split，这通常只在树状结构中才需要。

您可以生成这样的排列：

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 ...
 λ> 
 λ> import System.Random
 λ> import Control.Monad
 λ> import Control.Monad.Random
 λ> import System.Random.Shuffle
 λ> 
 λ> :type replicateM
 replicateM :: Applicative m => Int -> m a -> m [a]
 λ> 
 λ> :type shuffleM
 shuffleM :: MonadRandom m => [a] -> m [a]
 λ> 
 λ> action n k = replicateM k (shuffleM [1..n])
 λ> 
 λ> :type  action 10 6
 action 10 6 :: (MonadRandom m, Num a, Enum a) => m [[a]]
 λ> 
 λ> randomSeed = 42
 λ> gen0 = mkStdGen randomSeed
 λ> 
 λ> (xss,gen1) = runRand (action 10 6) gen0
 λ> 
 λ> printAsLines zs = mapM_  (putStrLn . show)  zs
 λ> 
 λ> printAsLines xss
 [10,7,4,6,3,9,1,8,2,5]
 [4,1,3,2,7,8,10,9,6,5]
 [2,8,6,9,1,5,7,4,3,10]
 [7,10,5,2,9,1,6,4,8,3]
 [3,7,4,10,8,1,2,5,6,9]
 [9,1,2,4,3,8,7,6,5,10]
 λ>

为什么 `fst (Random.split gen)` 返回的生成器有时会产生与 `gen` 相同的结果？

Why does the generator returned by `fst (Random.split gen)` sometimes produce the same results as `gen`?

haskell