我假设目标是实现以下算法:我们有一种随机生成器,可以将其视为以某种方式产生一系列随机值的流程。
import Pipes
prng :: Monad m => Producer Int m r
我们希望通过使用一个洗牌盒子来修改这个伪随机数生成器。洗牌盒子有一个可变状态的
Box
,它是一个随机整数数组,并且以特定方式修改随机整数流。请注意,保留HTML标记。
shuffle :: Monad m => Box -> Pipe Int Int m 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
是一个可变的ST
Vector
,链接到s
ST
线程。我们可以立即使用这个来构建我们的洗牌算法,现在知道Monad
m
必须实际为ST s
。
import Control.Monad
shuffle :: Box s -> Pipe Int Int (ST s) r
shuffle box = forever $ do
up <- await
next <- lift $ do let index = up `rem` sz box
prior <- Vm.read (vc box) index
Vm.write (vc box) index up
return prior
yield next
现在我们想将这个shuffle
附加到一些prng
Producer
上。由于我们使用的是vector
,因此最好使用高性能的mwc-random
库。
import qualified System.Random.MWC as MWC
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
中的类型都各自非常通用,因此一开始可能会很难理解。希望上述内容会更易于理解,我特意将几乎每种类型都弱化和专门化为这个确切的问题,并提供了一点关于这些精彩库如何单独和共同工作的直觉。
mwc-random
和vector
的可变向量之上实现了这一目标,但这种机制比您在此处看到的要复杂得多。 - J. Abrahamsonvector
、mwc-random
和pipes
写一个回复吧。我相信它可以实现你想要的功能,如果你忽略一些高度通用的类型,阅读起来也不是太难。 - J. Abrahamson