haskell - 为什么 `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，然后将其返回值之一传递给 shuffle'，将另一个传递给递归调用.