equal
deleted
inserted
replaced
1 structure Example : sig |
|
2 val fold : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b |
|
3 val rev : 'a list -> 'a list |
|
4 datatype 'a queue = AQueue of 'a list * 'a list |
|
5 val empty : 'a queue |
|
6 val dequeue : 'a queue -> 'a option * 'a queue |
|
7 val enqueue : 'a -> 'a queue -> 'a queue |
|
8 end = struct |
|
9 |
|
10 fun fold f (x :: xs) s = fold f xs (f x s) |
|
11 | fold f [] s = s; |
|
12 |
|
13 fun rev xs = fold (fn a => fn b => a :: b) xs []; |
|
14 |
|
15 datatype 'a queue = AQueue of 'a list * 'a list; |
|
16 |
|
17 val empty : 'a queue = AQueue ([], []); |
|
18 |
|
19 fun dequeue (AQueue ([], [])) = (NONE, AQueue ([], [])) |
|
20 | dequeue (AQueue (xs, y :: ys)) = (SOME y, AQueue (xs, ys)) |
|
21 | dequeue (AQueue (v :: va, [])) = |
|
22 let |
|
23 val y :: ys = rev (v :: va); |
|
24 in |
|
25 (SOME y, AQueue ([], ys)) |
|
26 end; |
|
27 |
|
28 fun enqueue x (AQueue (xs, ys)) = AQueue (x :: xs, ys); |
|
29 |
|
30 end; (*struct Example*) |
|