Fisher-Yates shuffle (Haskell)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Erlang | Forth | Haskell

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).

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.

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
Personal tools