Haskell рекурсия со случайными числами и IO - PullRequest
Новая
       14

Haskell рекурсия со случайными числами и IO

5 голосов
/ 10 мая 2011

Для 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

Насколько я могу сказать, это работает, но что яобеспокоены эти последние две строки.Я новичок в этом, и я не знаю, связанные с этим затраты оператора '<-' - это многократный вход или выход из ввода-вывода, как я делаю.Является ли это эффективным, есть ли лучший способ сделать это, который не включает в себя перенаправление ввода-вывода, или нет реальных накладных расходов? </p>

Любое понимание, которое у вас есть, ценится, так как я только недавно начал изучать этиболее сложные концепции в Haskell и еще не привыкшие к рассуждениям о системе ввода-вывода Haskell.

ОБЪЯСНЕНИЕ: Для этого я решил, что мне следует случайно выбрать один элемент из списка, используя функцию randomR(возвращает случайное число в заданном диапазоне) и продолжайте делать это рекурсивно, пока я не выберу n элементов.

Я сделал пару предположений о проблеме, которые привели меня к такому подходу.Во-первых, я предположил, что rndSelect может выбрать определенный элемент из списка только один раз, а во-вторых, я предположил, что каждый элемент должен иметь одинаковую вероятность быть выбранным.

PS: это мой первый вопрос о SO, поэтому, если я отформатировал вопрос, не стесняйтесь, сообщите мне.

Ответы [ 2 ]

3 голосов
/ 10 мая 2011

Для этого вам не нужен 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)

Если вас беспокоят издержки при переходе от ввода-вывода к чистому коду, не беспокойтесь.Вместо этого вы можете попробовать пакет mwc-random, который в этом случае будет как минимум на порядок быстрее.Кроме того, вы можете получить дополнительное преимущество, используя любую структуру данных с произвольным доступом вместо списка, если у вас много элементов.

1 голос
/ 10 мая 2011

Вы можете избежать ввода-вывода как: 

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
...