ex/insort.ML

update tags

(*  Title: 	HOL/ex/insort.ML
    ID:         $Id$
    Author: 	Tobias Nipkow
    Copyright   1994 TU Muenchen

Correctness proof of insertion sort.
*)

val insort_ss = sorting_ss addsimps
 [InSort.ins_Nil,InSort.ins_Cons,InSort.insort_Nil,InSort.insort_Cons];

goalw InSort.thy [Sorting.total_def]
  "!!f. [| total(f); ~f(x,y) |] ==> f(y,x)";
by(fast_tac HOL_cs 1);
val totalD = result();

goalw InSort.thy [Sorting.transf_def]
  "!!f. [| transf(f); f(b,a) |] ==> !x. f(a,x) --> f(b,x)";
by(fast_tac HOL_cs 1);
val transfD = result();

goal InSort.thy "list_all(p,ins(f,x,xs)) = (list_all(p,xs) & p(x))";
by(list_ind_tac "xs" 1);
by(asm_simp_tac insort_ss 1);
by(asm_simp_tac (insort_ss setloop (split_tac [expand_if])) 1);
by(fast_tac HOL_cs 1);
val insort_ss = insort_ss addsimps [result()];

goal InSort.thy "(!x. p(x) --> q(x)) --> list_all(p,xs) --> list_all(q,xs)";
by(list_ind_tac "xs" 1);
by(ALLGOALS(asm_simp_tac (insort_ss setloop (split_tac [expand_if]))));
val list_all_imp = result();

val prems = goal InSort.thy
  "[| total(f); transf(f) |] ==>  sorted(f,ins(f,x,xs)) = sorted(f,xs)";
by(list_ind_tac "xs" 1);
by(ALLGOALS(asm_simp_tac (insort_ss setloop (split_tac [expand_if]))));
by(cut_facts_tac prems 1);
by(cut_inst_tac [("p","f(xa)"),("q","f(x)")] list_all_imp 1);
by(fast_tac (HOL_cs addDs [totalD,transfD]) 1);
val insort_ss = insort_ss addsimps [result()];

goal InSort.thy "!!f. [| total(f); transf(f) |] ==>  sorted(f,insort(f,xs))";
by(list_ind_tac "xs" 1);
by(ALLGOALS(asm_simp_tac insort_ss));
result();