Haskell的遞歸利用隨機數和IO

對於99個Haskell的問題，特別是23rd一個，我需要Haskell的遞歸利用隨機數和IO

「從列表中提取隨機選擇的元件的給定數目。

實施例（在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：這是我的SO所以如果我格式化的問題隨時不佳告訴我好了第一個問題。

來源

2011-05-10 Dave

你真的需要包裝的結果IO單子？爲什麼不能：rndSelect ::（RandomGen g）=> [a] - > Int - > g - > [a] ....如果需要使用返回函數，此函數的用戶可以將結果列表包裝在IO中。 – Ankur 2011-05-10 05:28:31

我使用IO是因爲這是獲得隨機數字的唯一方法（我知道）。我希望從列表中隨機選擇/刪除一個元素，然後返回列表，以便我可以再次執行此操作（n-1）次。由於Haskell的純潔性，我認爲我不能在IO單子之外做到這一點，但也許可以編寫一個不使用IO的幫助函數。 – Dave 2011-05-10 05:37:10

你不需要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隨機包，在這種情況下，它至少要快一個數量級。此外，如果您有很多元素，您可以使用任何隨機訪問數據結構而不是列表獲得額外的好處。

來源

2011-05-10 05:52:06 aleator

對，我明白了。我感到困惑，並認爲我需要IO，因爲我正在閱讀關於LYAH中的getStdGen，當時我需要的就是種子randomGen。 >如果你關心的開銷從IO要純代碼，不要。謝謝。這個計劃的優化並不重要，因爲要知道IO是否與成本有關，所以這很好理解。 – Dave 2011-05-10 06:08:19

你能避免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

來源

2011-05-10 06:00:22 Ankur

謝謝，我剛剛得到了aleator的回答，但你說得對，因爲我錯誤地認爲我需要IO。 – Dave 2011-05-10 06:12:20

Haskell的遞歸利用隨機數和IO

回答

相關問題