Robert Kooima

Pseudo-random number generation is troublesome in a pure functional language like Haskell. PRNGs work by repeatedly mangling a piece of persistent state which, in imperative languages, is usually a simple global. To support such an operation in Haskell, one either needs to use the PRNG in the IO monad, or pass the state around explicitly.

With that in mind, we turn to the problem of list shuffling. Given a list, return a copy of the list with the elements randomly reordered. The great Oleg Kiselyov discusses the problem here. Oleg provides two solutions: a straightforward O(n²) solution, and a more sophisticated O(n log n) approach using binary trees.

The sophisticated approach is a little verbose IMO, and it seemed that an equally efficient yet more terse example could result from the realization that list shuffling resembles the Quicksort algorithm. If you replace the value test with a random outcome, the result should be a random ordering of the list in O(n log n) time. Here’s an implementation:

import Random

shuffle xs g = fst (mix xs (randomRs (True, False) g))

    where mix [ ] r0 = ([ ], r0)
          mix [x] r0 = ([x], r0)
          mix  xs r0 = let (ys, zs, r1) = cut xs r0 [] []
                           (cs,     r2) = mix ys r1
                           (ds,     r3) = mix zs r2
                       in  (cs++ds, r3)

          cut    []     rs  ys zs = (ys, zs, rs)
          cut (x:xs) (r:rs) ys zs = if r then cut xs rs (x:ys) zs
                                         else cut xs rs ys (x:zs)

The cut function randomly distributes the elements of a list between two new lists. The mix function recursively shuffles these two new lists and concatenates the results. The shuffle function takes a Haskell StdGen which it uses to produce an infinite list of pseudo-random booleans. Note that this list of booleans must be passed to and returned from every function internally. Such is the cost of pure functional code. Use it like this:

*Main Random> shuffle [1..10] (mkStdGen 3)
[1,6,2,5,4,10,3,8,7,9]
*Main Random> shuffle [1..10] (mkStdGen 10)
[2,1,5,3,6,7,10,8,4,9]