Haskell递归与随机数和IO

Question

Haskell递归与随机数和IO

5

对于99个Haskell问题，特别是第23个问题，我需要从列表中提取给定数量的随机选择元素。

(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：这是我在SO上的第一个问题，如果我格式化问题不好，请随时告诉我。

- Dave

你真的需要将结果包装在IO单子中吗？为什么不能是：rndSelect ::（RandomGen g）=> [a] -> Int -> g-> [a] ....此函数的用户可以使用return函数在需要时将结果列表包装在IO中。 - Ankur

1

我使用IO，因为那是我所知道的唯一获取随机数的方法。我希望能够从列表中随机选择/删除一个元素，然后返回该列表，以便我可以再次执行此操作（n-1）次。由于Haskell的纯度，我认为我不能在IO单子之外完成这个操作，但可能可以编写一个不使用IO的辅助函数来实现。 - Dave

2个回答

1

您可以避免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

- Ankur

谢谢，我刚刚得到了aleator的答案，但你说得对，我错误地认为我需要IO。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aleator · Accepted Answer

针对此问题，您并不需要输入输出（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包，在这种情况下至少会快一个数量级。此外，如果你有许多元素，使用任何随机访问数据结构而不是列表可能会带来额外的好处。