Haskell recursión con números aleatorios y IO

Question

para el 99 preguntas Haskell, específicamente la 23rd uno, necesito

"Extracto de un número dado de elementos seleccionados al azar de una lista.

Ejemplo (en Lisp) :

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

"

Qué he implementado este modo:

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 

Hasta donde puedo decir que esto funciona, pero lo que me preocupa son esas dos últimas líneas. Soy nuevo en esto y no sé los costos asociados del operador '< -' es o rebote dentro y fuera de IO repetidamente como lo estoy haciendo. ¿Es esto eficiente, hay una mejor manera de hacer esto que no implique rebotar IO, o no hay gastos generales involucrados?

Cualquier idea que tenga se agradece, ya que recientemente he empezado a aprender estos conceptos más sofisticados en Haskell y aún no me he acostumbrado a razonar sobre el sistema IO de Haskell.

EXPLICACIÓN: Para hacer esto, he decidido que debería seleccionar aleatoriamente un elemento de la lista usando la función randomR (devuelve un número aleatorio en un rango dado), y sigo haciendo esto recursivamente hasta que haya tomado n elementos.

He hecho un par de suposiciones sobre el problema que me ha llevado a este enfoque. En primer lugar, he supuesto que rndSelect puede seleccionar un elemento específico de la lista solo una vez y, en segundo lugar, he supuesto que cada elemento debería tener la misma probabilidad de ser elegido.

PD: es mi primera pregunta en SO, así que si he formateado la pregunta, no dude en decirme.

Answer 1

No necesita IO para esto, ya que randomR no lo requiere. Lo que hay que hacer sin embargo, es para enhebrar el generador de números aleatorios a través de su cálculo:

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) 

Si usted está preocupado acerca de los gastos generales que van de IO con código puro, no se. En su lugar, puedes probar el paquete mwc-random, que será al menos un orden de magnitud más rápido en este caso. Además, podría obtener un beneficio adicional utilizando cualquier estructura de datos de acceso aleatorio en lugar de la lista si tiene muchos elementos.

Answer 2

Puede evitar IO como:

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