# 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
```

```# 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
```

```# 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], [])
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]
```