使用随机数和 IO 的 Haskell 递归

Question

对于 99 个 Haskell 问题，特别是 第 23 个问题，我需要

“提取给定的数字”从列表中随机选择的元素。

示例（在 lisp 中）：

(rnd-select '(a b c d e f g h) 3)
(E D A)

“

我已经这样实现了：

import System.Random
import Control.Monad

removeAt :: [a] -> Int -> [a]
removeAt (x:xs) i
    | i > 0  = x : removeAt xs (i-1)
    | otherwise = xs

rndSelect :: (RandomGen g) => [a] -> Int ->  g -> IO [a]
rndSelect _ 0 _ = return []
rndSelect xs n gen = do
    let (pos, newGen) = randomR (0, length xs - 1) gen
    rest <- rndSelect (removeAt xs pos) (n-1) newGen
    return $ (xs!!pos):rest

-- for an explanation of what this is doing see EXPLANATION below

据我所知，这是可行的，但我关心的是最后两行。我对此很陌生，我不知道“<-”运算符的相关成本是或像我一样反复进出 IO。这是否有效，是否有更好的方法来做到这一点，不涉及反弹 IO，或者不涉及真正的开销？

感谢您的任何见解，因为我最近才开始学习 Haskell 中的这些更复杂的概念，并且还没有习惯对 Haskell 的 IO 系统进行推理。

说明：为了做到这一点，我决定应该使用 randomR 函数从列表中随机选择一个元素（返回给定范围内的随机数），并继续递归执行此操作，直到获取 n 个元素。

我对导致我采用这种方法的问题做出了一些假设。首先，我假设 rndSelect 只能从列表中选择一个特定元素一次，其次，我假设每个元素应该有相同的被选择概率。

PS：这是我的第一个问题，所以如果我的问题格式不好，请随时告诉我。

Answer 1

为此，您不需要 IO，因为 randomR 不需要它。然而，您需要做的是将随机数生成器贯穿您的计算：

import System.Random
import Control.Monad

removeAt :: [a] -> Int -> [a]
removeAt (x:xs) i
    | i > 0  = x : removeAt xs (i-1)
    | otherwise = xs


rndSelect :: (RandomGen t, Num a) => [a1] -> a -> t -> ([a1], t)
rndSelect _ 0 g = ([],g)
rndSelect xs n gen =
   let (pos, newGen) = randomR (0, length xs - 1) gen
       (rest,ng)     = rndSelect (removeAt xs pos) (n-1) newGen
   in  ((xs!!pos):rest, ng)

如果您担心从 IO 到纯代码的开销，请不要担心。相反，您可以尝试 mwc-random 包，在这种情况下，速度至少会快一个数量级。此外，如果您有许多元素，您可以使用任何随机访问数据结构而不是列表获得额外的好处。

Answer 2

您可以避免 IO，如下所示：

rndSelect :: (RandomGen g) => [a] -> Int ->  g -> [a]
rndSelect _ 0 _ = return []
rndSelect xs n gen = do
    let (pos, newGen) = randomR (0, length xs - 1) gen
         rest = rndSelect (removeAt xs pos) (n-1) newGen
    in (xs!!pos):rest