[Haskell-beginners] randomize the order of a list

27 Aug 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

[Haskell-beginners] randomize the order of a list

Gaius Hammond