Posted By

rtperson on 09/10/11


Tagged

problems 99 randomization


Versions (?)

Haskell 99 Problems - Problem 23


 / Published in: Haskell
 

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

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
  1. -- ah, randomization. Always fun in Haskell.
  2. -- this selects only one letter. Not what we want...
  3. rnd_select_one :: [a] -> IO [a]
  4. rnd_select_one xs = do
  5. let len = (length xs) - 1
  6. n <- randomRIO (0, len)
  7. return [(xs!!n)]
  8.  
  9. -- this version allows resampling.
  10. rnd_select :: [a] -> Int -> IO [a]
  11. rnd_select xs n = do
  12. g <- sequence (replicate n (rnd_select_one xs))
  13.  
  14. -- Here's how to prevent re-sampling, using partition from Data.List
  15. -- like so:
  16. -- partition (`elem` "g") "abcdefghijklmn"
  17. -- --> ("g", "abcdefhijklmn")
  18. --
  19. -- It would also be fairly trivial to use removeAt from Problem 20
  20.  
  21.  
  22. rnd_select_one' :: Eq a => ([a], [a]) -> Int -> IO ([a], [a])
  23. rnd_select_one' (acc, xs) 0 = return (acc, xs)
  24. rnd_select_one' (acc, []) _ = return (acc, [])
  25. rnd_select_one' (acc, xs) n = do
  26. let len = (length xs) - 1
  27. d <- randomRIO (0, len)
  28. let el = (xs!!d)
  29. let (g, ys) = partition (`elem` [el]) xs
  30. let ret = (acc ++ g, ys)
  31. rnd_select_one' ret (n-1)
  32.  
  33. rnd_select' :: Eq a => [a] -> Int -> IO [a]
  34. rnd_select' xs n = do
  35. j <- rnd_select_one' ([], xs) n
  36. return $ fst j

Report this snippet  

You need to login to post a comment.