Fisher-Yates shuffle (Haskell)
From LiteratePrograms
The Fisher-Yates shuffle is the most used algorithm for shuffling lists or arrays. In its original wording, you should get a random element from the original list into an accumulator until the original list is empty. In practice, a more convoluted wording is commonly used, which shuffles a list in-place:
- Let A be the list, N be its length, A1–AN be its elements. Let i be N.
- Let r be random between 1 and i (inclusive).
- If i is not equal to r, swap Ar and Ai.
- Decrease i by one.
- Repeat steps 2 through 4 until i equals 1.
The algorithm complexity is O(n).
Note that a better implementation is described here.
Since lists in Haskell are not like arrays and not efficient at changing certain elements by their ordinal number, the original wording by Fisher and Yates is perhaps preferred.
We'll need an accumulator for storing a shuffled piece of the list, so we define our main shuffle function with a helper 2-arguments shuffle' function.
<<shuffle.hs>>= import System.Random shuffle :: [a] -> IO [a] shuffle l = shuffle' l [] where shuffle'
If we ran out of the list, we have the result in the accumulator.
<<shuffle'>>= shuffle' [] acc = return acc
Else we split the list randomly so that the second resulting list contained at least 1 element in the head and put this element into the accumulator, that is drawing a random element from the list such way, and then tail-recursively shuffle the rest.
<<shuffle'>>= shuffle' l acc = do k <- randomRIO (0, length l - 1) let (lead, x:xs) = splitAt k l shuffle' (lead ++ xs) (x:acc)
| Download code |