Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Haskell

Idiom #158 Random sublist

Create a new list y from randomly picking exactly k elements from list x.

It is assumed that x has at least k elements.
Each element must have same probability to be picked.
Each element from x must be picked at most once.
Explain if the original ordering is preserved or not.

import System.Random (randomRIO)
randomSample :: Int -> [a] -> IO [a]
randomSample 0 x = pure []
randomSample k x = do
   i <- randomRIO (0, length x - 1)
   let (a, e:b) = splitAt i x
   l <- randomSample (k-1) (a ++ b)
   pure (e : l)

Haskell doesn't allow non-deterministic functions. We have to use the IO type to let it know we'll only us this in an I/O context.
(def y (->> x shuffle (take k)))

New implementation...
< >
programming-idioms.org