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.
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
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
- Indexing into a list is O(n), so every call to
xs !! indexadds 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
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.