structure Example : sig
val fold : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
val rev : 'a list -> 'a list
datatype 'a queue = AQueue of 'a list * 'a list
val empty : 'a queue
val dequeue : 'a queue -> 'a option * 'a queue
val enqueue : 'a -> 'a queue -> 'a queue
end = struct
fun fold f (x :: xs) s = fold f xs (f x s)
| fold f [] s = s;
fun rev xs = fold (fn a => fn b => a :: b) xs [];
datatype 'a queue = AQueue of 'a list * 'a list;
val empty : 'a queue = AQueue ([], []);
fun dequeue (AQueue ([], [])) = (NONE, AQueue ([], []))
| dequeue (AQueue (xs, y :: ys)) = (SOME y, AQueue (xs, ys))
| dequeue (AQueue (v :: va, [])) =
let
val y :: ys = rev (v :: va);
in
(SOME y, AQueue ([], ys))
end;
fun enqueue x (AQueue (xs, ys)) = AQueue (x :: xs, ys);
end; (*struct Example*)