Write a function to extract a given number of randomly selected elements from a list

I’m going through the 99 Haskell problems and I have a few question about the solution I implemented for Problem 23.

It asks:

Extract a given number of randomly selected elements from a list.

This is the code I came up with:

-- Extract a given number of randomly selected elements from a list.
import System.Random

randomFromList :: StdGen -> Int -> [a] -> ([a], StdGen)

randomFromList generator 0 _ = ([], generator)
randomFromList generator toDo xs =
  let (nextInt, generator') = next generator
      index = mod nextInt (length xs)
      (otherNumbers, generator'') = randomFromList generator' (toDo -1) xs
  in  ((xs !! index) : otherNumbers, generator'')

It works, but I’m not sure this is idiomatic Haskell nor that it is the best way to address this problem.

None of the solutions in the Haskell wiki uses the let approach so I was wondering if it is discouraged for some reason.

Your solution looks good to me, no reason to discourage using let as far as I know.

Tip: if you make the type randomFromList :: Int -> [a] -> StdGen -> ([a], StdGen), then you can call it like this: main = getStdGen >>= print . randomFromList 7 ['A'..'Z']

Also, if the requirement is interpreted as selecting randomly without replacement, your version only needs slight modification (this also uses randomR rather than mod):

dropAt :: Int -> [a] -> [a]
dropAt k xs = take k xs ++ drop (k+1) xs

randomFromList :: Int -> [a] -> StdGen -> ([a], StdGen)
randomFromList 0 _ generator = ([], generator)
randomFromList _ [] generator = ([], generator)
randomFromList toDo xs generator =
  let (index, generator') = randomR (0, length xs - 1) generator
      (otherNumbers, generator'') = randomFromList  (toDo -1) (dropAt index xs) generator'
  in  ((xs !! index) : otherNumbers, generator'')

See also this shuffle implementation for some attempt at optimisation. (You could potentially solve the random selection by something like take n . shuffle.)

There is no reason against using let in this case. Some people actually prefer it over where so that the code can be read top down.

I’d like to point out that the time complexity of your algorithm is O(n^2). There are two reasons:

1. At every step you’re computing length xs again.
2. Indexing into a list is O(n), so every call to xs !! index adds O(n).

Number (1) is easy to solve, you need to compute length xs only once and share it within the computation. You could use nested let or where (or their combination), or separate the computation into multiple functions.

Number (2) is somewhat harder. One solution would be to create an array from the list first one, that is O(n) (see listArray), and then use ! to look up elements in O(1). If the number of required elements k is small compared to the length of the list n, you could try to devise an algorithm that’d use this advantage and work in O(n k) or perhaps even O(n log k), still keeping the uniform distribution of the elements in the returned list – this looks like a nice exercise.

Also in the case you’d like to use monadic computations, have a look at MonadRandom, which eliminates the problem of passing the random generator around.