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

Posted on

Problem

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

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.

Solution

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.