Fisher-Yates shuffle i SML

fisher-yates.sml

;load "Random";

local
  val rng = Random.newgen ()

  (* elemFun xs 0 omdanner en liste xs til en funktion f
   * Dvs, f i = x, hvis x er på plads i i xs. *)
  fun elemFun []      _ _ = raise Domain
    | elemFun (x::xs) i n = if n = i then x else elemFun xs (i+1) n

  (* ombytter elementerne på plads i og j i liste-funktionen fxs. *)
  fun swap fxs i j n = fxs (if n = i then j else if n = j then i else n)

  (* laver en Fisher-Yates shuffle af fxs *)
  fun doSwaps fxs 0 = fxs
    | doSwaps fxs n =
        doSwaps (swap fxs n (Random.range (0, n+1) rng)) (n-1)
in
  (* blander listen xs med en Fisher-Yates shuffle *)
  fun shuffle xs =
    let val l = length xs in
      List.tabulate (l, doSwaps (elemFun xs 0) (l-1))
    end
end