Posted By

rtperson on 09/10/11

Tagged

Versions (?)

Last Edited at 09/10/11 07:27am

Statistics

Viewed 578 times

Favorited by 0 user(s)

Related snippets

Haskell 99 Problems - Problem 23

/ Published in: Haskell

problem 23, Extract a given number of randomly selected elements from a list.
Example:

Prelude System.Random>rnd_select "abcdefgh" 3 >>= putStrLn

"eda"

Two problems: 1) How to return a list, and 2) how to sample without duplication

Highlighted TextExpand

-- ah, randomization. Always fun in Haskell.
-- this selects only one letter. Not what we want...
rnd_select_one :: [a] -> IO [a]
rnd_select_one xs = do
    let len = (length xs) - 1
    n <- randomRIO (0, len)
    return [(xs!!n)]

-- this version allows resampling. 
rnd_select :: [a] -> Int -> IO [a]
rnd_select xs n = do
    g <- sequence (replicate n (rnd_select_one xs))
    return (concat g)

-- Here's how to prevent re-sampling, using partition from Data.List
-- like so: 
-- partition (`elem` "g") "abcdefghijklmn"
--  --> ("g", "abcdefhijklmn")
--
-- It would also be fairly trivial to use removeAt from Problem 20

rnd_select_one' :: Eq a => ([a], [a]) -> Int -> IO ([a], [a])
rnd_select_one' (acc, xs) 0 = return (acc, xs)
rnd_select_one' (acc, []) _ = return (acc, [])
rnd_select_one' (acc, xs) n = do
    let len = (length xs) - 1
    d <- randomRIO (0, len)
    let el = (xs!!d)
    let (g, ys) = partition (`elem` [el]) xs
    let ret = (acc ++ g, ys)
    rnd_select_one' ret (n-1)

rnd_select' :: Eq a => [a] -> Int -> IO [a]
rnd_select' xs n = do
    j <- rnd_select_one' ([], xs) n
    return $ fst j

URL: http://haskell.org/haskellwiki/99_questions/21_to_28

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.