Fisher-Yates shuffle (Haskell)

From LiteratePrograms
Jump to: navigation, search

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:

  1. Let A be the list, N be its length, A1AN be its elements. Let i be N.
  2. Let r be random between 1 and i (inclusive).
  3. If i is not equal to r, swap Ar and Ai.
  4. Decrease i by one.
  5. Repeat steps 2 through 4 until i equals 1.

The algorithm complexity is O(n).

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.

import System.Random

shuffle :: [a] -> IO [a]
shuffle l = shuffle' l []

If we ran out of the list, we have the result in the accumulator.

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' l acc =
  do k <- randomRIO (0, length l - 1)
     let (lead, x:xs) = splitAt k l
     shuffle' (lead ++ xs) (x:acc)
Download code