arrays - 将 MonadRandom 与堆栈中的 ST 计算相结合

Question

我正在尝试写 Fisher-Yates使用可变数组进行随机播放。到目前为止，我有以下代码:

module Main where

import Control.Monad.Random
import Control.Monad.Primitive
import Control.Monad.ST

import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV

fisherYates :: (MonadRandom m, PrimMonad m) => MV.MVector (PrimState m) a -> m ()
fisherYates v = forM_ [0 .. l - 1] (\i -> do j <- getRandomR (i, l)
                                             MV.swap v i j)
  where l = MV.length v - 1

shuffle :: MonadRandom m => V.Vector a -> m (V.Vector a)
shuffle v = _ -- don't know how to write this

main :: IO ()
main = print . evalRand (shuffle . V.generate 10 $ id) $ mkStdGen 42

但是，我完全不确定如何定义 shuffle，它是围绕可变向量操作的“高级包装器”。看来(至少从我的理解来看)，我首先必须“运行”堆栈的随机“部分”，保存状态，运行 ST“部分”以获取不可变的向量，然后重新包装整个事情。此外，我知道我必须在某个地方使用解冻，但我的尝试却很失败。有人可以告诉我我错过了什么，以及我怎样才能做我想做的事吗？

Answer 1

我有两个建议给你:

• 选择正确的 monad 嵌套。
• 将 monad 实现与算法逻辑分开。

您试图最后运行随机 monad 并在内部使用 ST，因此您需要 ST 成为一种 monad 转换器。决定你的 monad 堆栈是什么样的 - 哪个 monad 是转换器，哪个是内部 monad？最简单的事情是将 ST monad 设为内部 monad，将随机 monad 设为转换器(很简单，因为您已经拥有了所有需要的包)。

现在制作一小组辅助函数。在这里它不会真正得到返回 - 对于复杂的项目来说，返回是巨大的。这是我想出的 monad 堆栈和助手:

{-# LANGUAGE RankNTypes #-}
module Main where

import System.Random (StdGen)
import Control.Monad.Random
import Control.Monad.Primitive
import Control.Monad.ST

import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV


type KozM s a = RandT StdGen (ST s) a

注意变压器是 RandT 和 ST 的内部单子(monad)。

rnd :: (Int,Int) -> KozM s Int
rnd = getRandomR

swp :: MV.MVector s a -> Int -> Int -> KozM s ()
swp v i j = lift (MV.swap v i j)

freeze :: MV.MVector s a -> KozM s (V.Vector    a)
thaw   :: V.Vector     a -> KozM s (MV.MVector s a)
freeze = lift . V.freeze
thaw   = lift . V.thaw

改变向量所需的所有操作。现在我们只需要运行这个 monad，这样我们就可以以某种方式逃到另一个有用的上下文。我注意到你之前硬编码了一个 RNG (42) - 我使用一个随机的，但无论哪个......

run :: (forall s. KozM s a) -> IO a -- Can be just `a` if you hard-code
                                    -- an RNG as done in the question
run m = do g <- newStdGen
           pure (runST (evalRandT m g))

最后我们可以使用这个 monad 来实现 f-y:

fisherYates :: MV.MVector s a -> KozM s ()
fisherYates v = forM_ [0 .. l - 1] (\i -> do j <- rnd (i, l)
                                             swp v i j)
  where l = MV.length v - 1

此时您可能感觉自己没有学到任何东西，希望 run 函数有帮助，但我可以理解您可能会觉得这变得冗长。这里需要注意的重要一点是，如果您处理上面的 monad 的管道，那么您的代码的其余部分可以有多干净，这样您就不会使用 lift 和模块限定符来污染可能的逻辑您实际要解决的复杂问题。

也就是说，这是令人印象深刻的洗牌:

shuffle :: V.Vector a -> KozM s (V.Vector a)
shuffle v = do
    vm <- thaw v
    fisherYates vm
    freeze vm

类型很重要。您之前在 shuffle 上调用了 evalRand，这意味着它将是某种 MonadRandom m，同时必须调用 runST - monad 的合并逻辑和算法逻辑简直伤脑筋。

主要内容无趣:

main :: IO ()
main = print =<< (run (shuffle (V.generate 10 id)) :: IO (V.Vector Int))

编辑:是的，您可以在保持方法更通用的同时做到这一点。在某些时候，您需要指定运行哪个 monad，否则您将无法使用 main 来执行它，但所有逻辑都可以使用 MonadRandom 和 PrimMonad 进行通用。

{-# LANGUAGE RankNTypes #-}
module Main where

import System.Random (StdGen)
import Control.Monad.Random
import Control.Monad.Primitive
import Control.Monad.ST

import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
type KozM s a = RandT StdGen (ST s) a

rnd  :: MonadRandom m => (Int, Int) -> m Int
rnd = getRandomR

swp :: PrimMonad m => MV.MVector (PrimState m)  a -> Int -> Int -> m ()
swp v i j = MV.swap v i j

-- freeze :: MV.MVector s a -> KozM s (V.Vector    a)
-- thaw   :: V.Vector     a -> KozM s (MV.MVector s a)
freeze :: PrimMonad m => MV.MVector (PrimState m) a -> m (V.Vector a)
thaw :: PrimMonad m => V.Vector a -> m (MV.MVector (PrimState m) a)
freeze = V.freeze
thaw   = V.thaw


-- Some monad libraries, like monadlib, have a generalized `run` class method.
-- This doesn't exist, to the best of my knowledge, for the intersection of ST
-- and mtl.
run :: (forall s. KozM s a) -> IO a -- Can be just `a` if you hard-code
                                    -- an RNG as done in the question
run m = do g <- newStdGen
           pure (runST (evalRandT m g))

-- fisherYates :: MV.MVector s a -> KozM s ()
fisherYates :: (MonadRandom m, PrimMonad m) => MV.MVector (PrimState m) a -> m ()
fisherYates v = forM_ [0 .. l - 1] (\i -> do j <- rnd (i, l)
                                             swp v i j)
  where l = MV.length v - 1

shuffle :: (MonadRandom m, PrimMonad m) => V.Vector a -> m (V.Vector a)
shuffle v = do
    vm <- thaw v
    fisherYates vm
    freeze vm

main :: IO ()
main = print =<< (run (shuffle (V.generate 10 id)) :: IO (V.Vector Int))