Haskell中的伪随机数生成器

Question

我正在解决最新的编程练习谜题——第一个是实现最小标准随机数生成器，第二个是实现一个洗牌盒，可以与该随机数生成器或其他伪随机数生成器配合使用。实现数学部分相当简单。对我来说棘手的部分是如何正确地将这些部分组合在一起。

概念上，伪随机数生成器是一个函数stepRandom :: s -> (s, a)，其中s是生成器的内部状态类型，a是随机选择的对象类型。例如，对于线性同余PRNG，我们可以有s = a = Int64，或者s = Int64且a = Double。这篇文章在PSE上展示了如何使用单子将PRNG状态穿透到随机计算中，并使用runRandom来运行具有特定初始状态（种子）的计算，做得相当不错。

从概念上讲，洗牌盒子是一个函数shuffle :: box -> a -> (box, a)，以及一个用来从PRNG中初始化所需大小的新盒子的函数。然而，在实践中，这个盒子的表示有点棘手。为了效率，它应该被表示为可变数组，这迫使它进入ST或IO。大致上像这样：

mkShuffle :: (Integral i, Ix i, MArray a e m) => i -> m e -> m (a i e)
mkShuffle size getRandom = do
  thelist <- replicateM (fromInteger.fromIntegral $ size) getRandom
  newListArray (0,size-1) thelist
shuffle :: (Integral b, Ix b, MArray a b m) => a b b -> b -> m b
shuffle box n = do
  (start,end) <- getBounds box
  let index = start + n `quot` (end-start+1)
  value <- readArray box index
  writeArray box index n
  return value

我真正想做的是将一个（已初始化的？）洗牌盒附加到一个伪随机数生成器上，以便将伪随机数生成器的输出“传送”到洗牌盒中。我不知道如何正确地设置这个连接。

- dfeuer

---

你确定你真的需要可变数组提供的效率吗？一个非装箱但不可变的数组可能已经足够了。 - icktoofay

哪个概念？可变数组还是“管道”？每个都可以很容易地单独演示，但一起使用可能会很复杂。如果目标是使用洗牌盒修改PRNG的输出，则我编写了一些代码，在mwc-random和vector的可变向量之上实现了这一目标，但这种机制比您在此处看到的要复杂得多。 - J. Abrahamson

@J.Abrahamson，管道以及如何将其与可变数组配合使用的方法。不幸的是，我可能还没有准备好这一点，我想：/. 在Haskell中的事情往往是“当然，我明白。好的，没问题。当然了。容易。等等！什么意思????” - dfeuer

那我就用 vector、mwc-random 和 pipes 写一个回复吧。我相信它可以实现你想要的功能，如果你忽略一些高度通用的类型，阅读起来也不是太难。 - J. Abrahamson

你可以使用ST单子并生成惰性列表。这样你就可以隐藏ST。 - augustss

Answer 1

我假设目标是实现以下算法：我们有一种随机生成器，可以将其视为以某种方式产生一系列随机值的流程。

import Pipes

prng :: Monad m => Producer Int m r  

-- produces Ints using the effects of m never stops, thus the 
-- return type r is polymorphic

我们希望通过使用一个洗牌盒子来修改这个伪随机数生成器。洗牌盒子有一个可变状态的Box，它是一个随机整数数组，并且以特定方式修改随机整数流。请注意，保留HTML标记。

shuffle :: Monad m => Box -> Pipe Int Int m r   

-- given a box, convert a stream of integers into a different 
-- stream of integers using the effects of m without stopping 
-- (polymorphic r)

shuffle 函数基于整数逐个操作，通过将随机值对盒子大小取模并索引到其 Box 中，将输入值存储在那里，并发出先前存储在那里的值。从某种意义上说，它类似于一种随机延迟函数。

---

因此，根据这个规格，让我们来实现一个真正的版本。我们想要使用可变数组，所以我们将使用 vector 库和 ST monad。 ST 要求我们传递一个幻影 s 参数，该参数在特定的 ST monad 调用中匹配，因此当我们编写 Box 时，它需要公开该参数。

import qualified Data.Vector.Mutable as Vm
import           Control.Monad.ST

data Box s = Box { sz :: Int, vc :: Vm.STVector s Int }

sz参数是Box内存的大小，Vm.STVector s是一个可变的STVector，链接到sST线程。我们可以立即使用这个来构建我们的洗牌算法，现在知道Monadm必须实际为ST s。

import           Control.Monad

shuffle :: Box s -> Pipe Int Int (ST s) r
shuffle box = forever $ do                          -- this pipe runs forever
  up <- await                                       -- wait for upstream
  next <- lift $ do let index = up `rem` sz box     -- perform the shuffle
                    prior <- Vm.read (vc box) index --   using our mutation
                    Vm.write (vc box) index up      --   primitives in the ST
                    return prior                    --   monad
  yield next                                        -- then yield the result

---

现在我们想将这个shuffle附加到一些prngProducer上。由于我们使用的是vector，因此最好使用高性能的mwc-random库。

import qualified System.Random.MWC   as MWC

-- | Produce a uniformly distributed positive integer
uniformPos :: MWC.GenST s -> ST s Int
uniformPos gen = liftM abs (MWC.uniform gen)

prng :: MWC.GenST s -> Int -> ST s (Box s)
prng gen = forever $ do 
  val <- lift (uniformPos gen)
  yield val

注意，由于我们正在通过MWC.GenST s传递PRNG种子，因此我们不需要捕获修改并将它们一起发送。相反，mwc-random在幕后使用可变的STRef s。还要注意，我们修改MWC.uniform仅返回正索引，因为这对于shuffle中的索引方案是必需的。

我们也可以使用mwc-random来生成我们的初始框。

mkBox :: MWC.GenST s -> Int -> ST s (Box s)
mkBox gen size = do 
  vec <- Vm.replicateM size (uniformPos gen)
  return (Box size vec)

这里唯一需要注意的是非常好用的 Vm.replicateM 函数，其类型受到限制：

Vm.replicateM :: Int -> ST s Int -> Vm.STVector s Int

第二个参数是一个ST s操作，它生成向量的一个新元素。

---

最后我们拥有了所有的部件。我们只需要将它们组装起来即可。幸运的是，使用pipes获得的模块化使这变得微不足道。

import qualified Pipes.Prelude       as P

run10 :: MWC.GenST s -> ST s [Int]
run10 gen = do
  box <- mkBox gen 1000
  P.toListM (prng gen >-> shuffle box >-> P.take 10)

在这里，我们使用(>->)来构建一个生产流水线，并使用P.toListM来运行该流水线并生成一个列表。最后，我们只需要在IO中执行这个ST s线程，这也是我们可以创建初始的MWC.GenST s种子并将其馈送到MWC.withSystemRandom中使用SystemRandom生成初始种子的地方。

main :: IO ()
main = do
  result <- MWC.withSystemRandom run10
  print result

现在我们有了我们的流水线。

*ShuffleBox> main
[743244324568658487,8970293000346490947,7840610233495392020,6500616573179099831,1849346693432591466,4270856297964802595,3520304355004706754,7475836204488259316,1099932102382049619,7752192194581108062]

请注意，这些部件的实际操作并不太复杂。不幸的是，ST、mwc-random、vector 和 pipes 中的类型都各自非常通用，因此一开始可能会很难理解。希望上述内容会更易于理解，我特意将几乎每种类型都弱化和专门化为这个确切的问题，并提供了一点关于这些精彩库如何单独和共同工作的直觉。

- J. Abrahamson

---

我至少需要一天或两天来理解这个。如果我能在最后理解了它，我会非常高兴接受这个答案。 - dfeuer

请注意，使用高质量的伪随机数发生器并不是关键点。关键是能够插入任何我想要的伪随机数发生器。有一件事让我有点担心：概念上，附加了洗牌盒的伪随机数发生器本身就是一个伪随机数发生器。我还不清楚你的代码是否反映了这一点。这可能只是因为我还没理解其中一半。 - dfeuer

这个实现反映了 prng 和 prng + shuffle 都是相同类型的事实。明确地说，我们可以看到 prng gen 和 prng gen >-> shuffle box 都具有类型 Producer Int (ST s) r，它的含义是 "在 ST monad 上产生整数"。 - J. Abrahamson

你可以继续执行以下操作，如果你愿意的话：prng gen >-> shuffle box1 >-> shuffle box2 >-> shuffle box3。 - J. Abrahamson

值得注意的是，只需更改 Box 和一些类型注释，整个示例就可以切换到 IO 而不是 ST。这就是为什么 mwc-random 和 vector 具有复杂的类型 - 它们对 IO 和 ST 是通用的。 - J. Abrahamson