Блог

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

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

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

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

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

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

Для этого вам не нужен 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 package, который в этом случае будет по крайней мере на порядок быстрее. Кроме того, вы могли бы получить дополнительную выгоду, используя любую структуру данных с произвольным доступом вместо списка, если у вас много элементов.

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

 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