[Haskell-beginners] randomize the order of a list
Gaius Hammond
gaius at gaius.org.uk
Fri Aug 27 16:02:59 EDT 2010
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
put g'
return v
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
| (r `elem` acc) ∨ (r ≡ (−1)) = do
r' ← randInt (x − 1)
randIndex' acc r'
| otherwise = do
r' ← randInt (x − 1)
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
More information about the Beginners
mailing list