How to easily shuffle a list in sml?

Question

How can I easily shuffle a list of tuples in sml? There doesn't seem to be any built in function to do so.

I assume I would need to use a random number generator but how you would move items in an list I have no idea.

Answer 1

This is for Moscow ML's Random library. For SML/NJ's Random library, you would have to adjust the random functions slightly.

val _ = load "Random"
val rng = Random.newgen ()

(* select([5,6,7,8,9], 2) = (7, [5,6,8,9]) *)
fun select (y::xs, 0) = (y, xs)
  | select (x::xs, i) = let val (y, xs') = select (xs, i-1) in (y, x::xs') end
  | select (_, i) = raise Fail ("Short by " ^ Int.toString i ^ " elements.")

(* Recreates a list in random order by removing elements in random positions *)
fun shuffle xs =
    let fun rtake [] _ = []
          | rtake ys max =
            let val (y, ys') = select (ys, Random.range (0, max) rng)
            in y :: rtake ys' (max-1)
            end
    in rtake xs (length xs) end