ならしコストによるキュー

SML 30分プログラム

30分プログラム、その715。ならしコストによるキューを作ってみる。
基本的にならしコストによるQueueを実装した - みずぴー日記の焼直しです。むしろ、いくつかの関数の実装をさぼってます。

あと、いまさらながらhttp://www.mpi-sws.org/~rossberg/sml-vs-ocaml.htmlが便利なことに気付きました。SMLの文法がコンパクトにまとまっているので、サクっと調べれます。

使い方

fun example () =
    let
	val q = enqueue "foo" (enqueue "bar" (enqueue "baz" empty))
	val (v1,q1) = dequeue q
	val (v2,q2) = dequeue q1
	val (v3,q3) = dequeue q2
    in
	println v1;
	println v2;
	println v3
    end;

ソースコード

type 'a queue = {
     front: 'a list,
     back : 'a list
}

val empty : 'a queue = { front=[], back=[] };
fun isEmpty q = q = empty

fun balance (q as {front=front, back=back}) =
    case front of
	[] => {front=List.rev back, back=[]}
      | _  => q;

fun enqueue v (q : 'a queue) = balance {
    front = #front q,
    back  = v :: (#back q)
};

fun dequeue (q : 'a queue) =
    case #front q of
	x::xs => (x,balance { front = xs, back = #back q })
      | [] => raise Empty;

fun println s =
    (print s;
     print "\n");

fun example () =
    let
	val q = enqueue "foo" (enqueue "bar" (enqueue "baz" empty))
	val (v1,q1) = dequeue q
	val (v2,q2) = dequeue q1
	val (v3,q3) = dequeue q2
    in
	println v1;
	println v2;
	println v3
    end;

参考