doc-src/Codegen/Thy/examples/example.ML

nicer code for rev

structure Example : sig
  val id : 'a -> 'a
  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 id x = (fn xa => xa) x;

fun fold f [] = id
  | fold f (x :: xs) = fold f xs o f x;

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*)