On Friday 27 August 2010 22:02:59, Gaius Hammond wrote:
Hi all,
I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My initial approach is to treat it as an array, generate a list of unique random numbers between 0 and n - 1, then use those numbers as new indexes. I am using a function to generate random numbers in the State monad as follows:
randInt∷ Int → State StdGen Int randInt x = do g ← get (v,g') ← return $ randomR (0, x) g
value <- return $ expression is always awkward. Bind it with a let: let value = expression
put g' return v
Here, it would be simpler to just write randInt x = State $ randomR (0,x)
This is pretty much straight from the documentation. My function for the new indexes is:
-- return a list of numbers 0 to x-1 in random order randIndex∷ Int → StdGen → ([Int], StdGen) randIndex x = runState $ do let randIndex' acc r
| (length acc ≡ x) = acc
If you need many random values, it would be faster to pass the number of values you still require as a parameter, that avoids traversing the list to get its length in each step.
| (r `elem` acc) ∨ (r ≡ (−1)) = do
You will get a skewed distribution of shuffles that way, that may or may not be a problem.
r' ← randInt (x − 1) randIndex' acc r'
| otherwise = do
r' ← randInt (x − 1) randIndex' r:acc r'
This is parsed as (randIndex' r) : (acc r') , remember, function application binds tightest. So the compiler sees a list and infers the type [a] for this do-block. Thus it would require (randInt x) to be a list too, of type [b]. However, it is of type (State StdGen Int). You need parentheses around the list pattern: randIndex' (r:acc) r'
in randIndex' [] (−1)
This fails to compile on
Couldn't match expected type `[a]' against inferred type `State StdGen b' In a stmt of a 'do' expression: r' <- randInt (x - 1) In the expression: do { r' <- randInt (x - 1); randIndex' acc r' }
I can see what's happening here - it's treating randIndex' as the second argument to randInt instead of invisibly putting the State in there. Or am I going about this completely the wrong way?
Thanks,
G