4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your comments. I really appreciate them. I usually care about having good performance but this was just a toy example and I didn't think at them. My bad, thanks for pointing it out \$\endgroup\$ – mariosangiorgio Sep 25 '14 at 20:46
  • \$\begingroup\$ @mariosangiorgio I pointed that out because it's a common mistake in Haskell programs when manipulating lists. Nevertheless, not caring about it can be perfectly fine, sometimes you just don't need to care about performance (like if the list is always at most 10 elements long). And it's definitely more important to have a correct program first and optimize performance later, than vice versa. \$\endgroup\$ – Petr Pudlák Sep 25 '14 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.