# 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
be the list,**A**be its length,**N**–**A**_{1}be its elements. Let**A**_{N}be**i**.**N** - Let
be random between 1 and**r**(inclusive).**i** - If
is not equal to**i**, swap**r**and**A**_{r}.**A**_{i} - Decrease
by one.**i** - Repeat steps 2 through 4 until
equals 1.**i**

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 |