リストのシャッフル

SML 30分プログラム

30分プログラム、その676。リストのシャッフルをやってみました。
簡単に書けると思いきや、意外と落とし穴にはまりました。

  • 乱数が生成できない!
    • FAQによると、Randomというアンドキュメントなstructureがあるらしい。
  • List.sortがない。
    • 自分で書いた。
  • fst,sndがない。
    • タプルはレコードの一種なので、#1,#2でアクセスできます。

使い方

- shuffle [1,2,3,4,5];
val it = [2,1,4,5,3] : int list
- shuffle [1,2,3,4,5];
val it = [4,3,1,5,2] : int list
- shuffle [1,2,3,4,5];
val it = [3,5,4,2,1] : int list
- shuffle [1,2,3,4,5];
val it = [2,1,5,4,3] : int list

ソースコード

fun srand () =
    let
	val d = Date.fromTimeLocal (Time.now ())
	val m = Date.minute d
	val s = Date.second d
    in
	Random.rand (m,s)
    end;

fun compare x y = if x < y then
		      LESS
		  else if x > y then
		      GREATER
		  else
		      EQUAL;

fun sort _ [] = []
  | sort f (x::xs) = sort f (List.filter (fn y => f y x = LESS) xs)
		     @ [ x ]
		     @ sort f (List.filter (fn y => f y x = GREATER) xs)

fun shuffle xs =
    let
	val rand = srand ()
	val ys   = List.map (fn x => (x,Random.randInt rand)) xs
	fun cmp (_,a) (_,b) = compare a b
	val zs = sort cmp ys
    in
	List.map #1 zs
    end;

参考