Problem

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.

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:

- At every step you’re computing
`length xs`

again. - 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.