How to randomly shuffle a list

Question

I have random number generator

rand :: Int -> Int -> IO Int
rand low high = getStdRandom (randomR (low,high))

and a helper function to remove an element from a list

removeItem _ []                 = []
removeItem x (y:ys) | x == y    = removeItem x ys
                    | otherwise = y : removeItem x ys

I want to shuffle a given list by randomly picking an item from the list, removing it and adding it to the front of the list. I tried

shuffleList :: [a] -> IO [a]
shuffleList [] = []
shuffleList l = do 
                     y <- rand 0 (length l)
                     return( y:(shuffleList (removeItem  y l) ) )

But can't get it to work. I get

hw05.hs:25:33: error:
    * Couldn't match expected type `[Int]' with actual type `IO [Int]'
    * In the second argument of `(:)', namely
     ....

Any idea ?

Thanks!

Answer 1

Generally, with Haskell it works better to maximize the amount of functional code at the expense of non-functional (IO or randomness-related) code.

In your situation, your “maximum” functional component is not removeItem but rather a version of shuffleList that takes the input list and (as mentioned by Will Ness) a deterministic integer position. List function splitAt :: Int -> [a] -> ([a], [a]) can come handy here. Like this:

funcShuffleList :: Int -> [a] -> [a]
funcShuffleList _ [] = []
funcShuffleList pos ls =
    if (pos <=0) || (length(take (pos+1) ls) < (pos+1))
      then ls -- pos is zero or out of bounds, so leave list unchanged
      else let (left,right) = splitAt pos ls
           in  (head right) : (left ++ (tail right))

Testing:

 λ> 
 λ> funcShuffleList  4  [0,1,2,3,4,5,6,7,8,9]
 [4,0,1,2,3,5,6,7,8,9]
 λ> 
 λ> funcShuffleList 5 "@ABCDEFGH"
 "E@ABCDFGH"
 λ> 

Once you've got this, you can introduce randomness concerns in simpler fashion. And you do not need to involve IO explicitely, as any randomness-friendly monad will do:

shuffleList :: MonadRandom mr => [a] -> mr [a]
shuffleList [] = return []
shuffleList ls =
    do
       let maxPos = (length ls) - 1
       pos <- getRandomR (0, maxPos)
       return (funcShuffleList pos ls)

... IO being just one instance of MonadRandom.

You can run the code using the default IO-hosted random number generator:

main = do
    let inpList = [0,1,2,3,4,5,6,7,8]::[Integer]

    putStrLn $ "inpList  = " ++ (show inpList)

    -- mr automatically instantiated to IO:
    outList1 <- shuffleList inpList
    putStrLn $ "outList1 = " ++ (show outList1)
    outList2 <- shuffleList outList1
    putStrLn $ "outList2 = " ++ (show outList2)

Program output:

$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [6,0,1,2,3,4,5,7,8]
outList2 = [8,6,0,1,2,3,4,5,7]
$ 
$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [4,0,1,2,3,5,6,7,8]
outList2 = [2,4,0,1,3,5,6,7,8]
$ 

The output is not reproducible here, because the default generator is seeded by its launch time in nanoseconds.

If what you need is a full random permutation, you could have a look here and there - Knuth a.k.a. Fisher-Yates algorithm.