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]