Queueの二通りの定義の仕方
シグネチャの定義
# module type QUEUE = sig type 'a t exception Empty val empty: 'a t val add: 'a t -> 'a -> 'a t val take: 'a t -> 'a * 'a t val peek: 'a t -> 'a end;; module type QUEUE = sig type 'a t exception Empty val empty : 'a t val add : 'a t -> 'a -> 'a t val take : 'a t -> 'a * 'a t val peek : 'a t -> 'a end
本体の定義その1
# module Queue1 : QUEUE = struct type 'a t = 'a list exception Empty let empty = [] let add q x = q @ [x] let take = function [] -> raise Empty | x :: rest -> (x, rest) let peek = function [] -> raise Empty | x :: rest -> x end;; module Queue1 : QUEUE
本体定義その2
# module Queue2 : QUEUE = struct type 'a t = Queue of ('a list * 'a list) exception Empty let empty = Queue ([], []) let add q x = match q with Queue ([], []) -> Queue ([x], []) | Queue (head, []) -> Queue (head, [x]) | Queue (head, tail) -> Queue (head, tail @ [x]) let take = function Queue ([], _) -> raise Empty | Queue (x :: [], tail) -> (x, Queue (tail, [])) | Queue (x :: rest, tail) -> (x, Queue (rest, tail)) let peek = function Queue ([], _) -> raise Empty | Queue (x :: _, _) -> x end;; module Queue2 : QUEUE
動作確認
# let rec trace1 q = try let (x, q') = Queue1.take q in x :: trace1 q' with Queue1.Empty -> [];; val trace1 : 'a Queue1.t -> 'a list = <fun> # let (<<<) q x = Queue1.add q x;; val ( <<< ) : 'a Queue1.t -> 'a -> 'a Queue1.t = <fun> # let q1 = Queue1.empty <<< 1 <<< 2 <<< 3 <<< 4 <<< 5 <<< 6 <<< 7;; val q1 : int Queue1.t = <abstr> # trace1 q1;; - : int list = [1; 2; 3; 4; 5; 6; 7] # let rec trace2 q = try let (x, q') = Queue2.take q in x :: trace2 q' with Queue2.Empty -> [];; val trace2 : 'a Queue2.t -> 'a list = <fun> # let (<<<) q x = Queue2.add q x;; val ( <<< ) : 'a Queue2.t -> 'a -> 'a Queue2.t = <fun> # let q2 = Queue2.empty <<< 1 <<< 2 <<< 3 <<< 4 <<< 5 <<< 6 <<< 7;; val q2 : int Queue2.t = <abstr> # trace2 q2;; - : int list = [1; 2; 3; 4; 5; 6; 7]