src/ZF/ex/BT_Fn.ML
changeset 7 268f93ab3bc4
parent 0 a5a9c433f639
child 29 4ec9b266ccd1
equal deleted inserted replaced
6:8ce8c4d13d4d 7:268f93ab3bc4
    10 
    10 
    11 
    11 
    12 
    12 
    13 (** bt_rec -- by Vset recursion **)
    13 (** bt_rec -- by Vset recursion **)
    14 
    14 
    15 (*Used to verify bt_rec*)
       
    16 val bt_rec_ss = ZF_ss 
       
    17       addcongs (mk_typed_congs BT_Fn.thy [("h", "[i,i,i,i,i]=>i")])
       
    18       addrews BT.case_eqns;
       
    19 
       
    20 goalw BT.thy BT.con_defs "rank(l) : rank(Br(a,l,r))";
    15 goalw BT.thy BT.con_defs "rank(l) : rank(Br(a,l,r))";
    21 by (SIMP_TAC rank_ss 1);
    16 by (simp_tac rank_ss 1);
    22 val rank_Br1 = result();
    17 val rank_Br1 = result();
    23 
    18 
    24 goalw BT.thy BT.con_defs "rank(r) : rank(Br(a,l,r))";
    19 goalw BT.thy BT.con_defs "rank(r) : rank(Br(a,l,r))";
    25 by (SIMP_TAC rank_ss 1);
    20 by (simp_tac rank_ss 1);
    26 val rank_Br2 = result();
    21 val rank_Br2 = result();
    27 
    22 
    28 goal BT_Fn.thy "bt_rec(Lf,c,h) = c";
    23 goal BT_Fn.thy "bt_rec(Lf,c,h) = c";
    29 by (rtac (bt_rec_def RS def_Vrec RS trans) 1);
    24 by (rtac (bt_rec_def RS def_Vrec RS trans) 1);
    30 by (SIMP_TAC bt_rec_ss 1);
    25 by (simp_tac (ZF_ss addsimps BT.case_eqns) 1);
    31 val bt_rec_Lf = result();
    26 val bt_rec_Lf = result();
    32 
    27 
    33 goal BT_Fn.thy
    28 goal BT_Fn.thy
    34     "bt_rec(Br(a,l,r), c, h) = h(a, l, r, bt_rec(l,c,h), bt_rec(r,c,h))";
    29     "bt_rec(Br(a,l,r), c, h) = h(a, l, r, bt_rec(l,c,h), bt_rec(r,c,h))";
    35 by (rtac (bt_rec_def RS def_Vrec RS trans) 1);
    30 by (rtac (bt_rec_def RS def_Vrec RS trans) 1);
    36 by (SIMP_TAC (bt_rec_ss addrews [Vset_rankI, rank_Br1, rank_Br2]) 1);
    31 by (simp_tac (ZF_ss addsimps 
       
    32 	      (BT.case_eqns @ [Vset_rankI, rank_Br1, rank_Br2])) 1);
    37 val bt_rec_Br = result();
    33 val bt_rec_Br = result();
    38 
    34 
    39 (*Type checking -- proved by induction, as usual*)
    35 (*Type checking -- proved by induction, as usual*)
    40 val prems = goal BT_Fn.thy
    36 val prems = goal BT_Fn.thy
    41     "[| t: bt(A);    \
    37     "[| t: bt(A);    \
    42 \       c: C(Lf);       \
    38 \       c: C(Lf);       \
    43 \       !!x y z r s. [| x:A;  y:bt(A);  z:bt(A);  r:C(y);  s:C(z) |] ==> \
    39 \       !!x y z r s. [| x:A;  y:bt(A);  z:bt(A);  r:C(y);  s:C(z) |] ==> \
    44 \		     h(x,y,z,r,s): C(Br(x,y,z))  \
    40 \		     h(x,y,z,r,s): C(Br(x,y,z))  \
    45 \    |] ==> bt_rec(t,c,h) : C(t)";
    41 \    |] ==> bt_rec(t,c,h) : C(t)";
    46 by (bt_ind_tac "t" prems 1);
    42 by (bt_ind_tac "t" prems 1);
    47 by (ALLGOALS (ASM_SIMP_TAC (ZF_ss addrews
    43 by (ALLGOALS (asm_simp_tac (ZF_ss addsimps
    48 			    (prems@[bt_rec_Lf,bt_rec_Br]))));
    44 			    (prems@[bt_rec_Lf,bt_rec_Br]))));
    49 val bt_rec_type = result();
    45 val bt_rec_type = result();
    50 
    46 
    51 (** Versions for use with definitions **)
    47 (** Versions for use with definitions **)
    52 
    48 
    96 
    92 
    97 
    93 
    98 val bt_typechecks =
    94 val bt_typechecks =
    99       [LfI, BrI, bt_rec_type, n_nodes_type, n_leaves_type, bt_reflect_type];
    95       [LfI, BrI, bt_rec_type, n_nodes_type, n_leaves_type, bt_reflect_type];
   100 
    96 
   101 val bt_congs = 
       
   102     BT.congs @
       
   103     mk_congs BT_Fn.thy ["bt_case","bt_rec","n_nodes","n_leaves","bt_reflect"];
       
   104 
       
   105 val bt_ss = arith_ss 
    97 val bt_ss = arith_ss 
   106     addcongs bt_congs
    98     addsimps BT.case_eqns
   107     addrews BT.case_eqns
    99     addsimps bt_typechecks
   108     addrews bt_typechecks
   100     addsimps [bt_rec_Lf, bt_rec_Br, 
   109     addrews [bt_rec_Lf, bt_rec_Br, 
       
   110 	     n_nodes_Lf, n_nodes_Br,
   101 	     n_nodes_Lf, n_nodes_Br,
   111 	     n_leaves_Lf, n_leaves_Br,
   102 	     n_leaves_Lf, n_leaves_Br,
   112 	     bt_reflect_Lf, bt_reflect_Br];
   103 	     bt_reflect_Lf, bt_reflect_Br];
   113 
   104 
   114 
   105 
   115 (*** theorems about n_leaves ***)
   106 (*** theorems about n_leaves ***)
   116 
   107 
   117 val prems = goal BT_Fn.thy
   108 val prems = goal BT_Fn.thy
   118     "t: bt(A) ==> n_leaves(bt_reflect(t)) = n_leaves(t)";
   109     "t: bt(A) ==> n_leaves(bt_reflect(t)) = n_leaves(t)";
   119 by (bt_ind_tac "t" prems 1);
   110 by (bt_ind_tac "t" prems 1);
   120 by (ALLGOALS (ASM_SIMP_TAC bt_ss));
   111 by (ALLGOALS (asm_simp_tac bt_ss));
   121 by (REPEAT (ares_tac [add_commute, n_leaves_type] 1));
   112 by (REPEAT (ares_tac [add_commute, n_leaves_type] 1));
   122 val n_leaves_reflect = result();
   113 val n_leaves_reflect = result();
   123 
   114 
   124 val prems = goal BT_Fn.thy
   115 val prems = goal BT_Fn.thy
   125     "t: bt(A) ==> n_leaves(t) = succ(n_nodes(t))";
   116     "t: bt(A) ==> n_leaves(t) = succ(n_nodes(t))";
   126 by (bt_ind_tac "t" prems 1);
   117 by (bt_ind_tac "t" prems 1);
   127 by (ALLGOALS (ASM_SIMP_TAC (bt_ss addrews [add_succ_right])));
   118 by (ALLGOALS (asm_simp_tac (bt_ss addsimps [add_succ_right])));
   128 val n_leaves_nodes = result();
   119 val n_leaves_nodes = result();
   129 
   120 
   130 (*** theorems about bt_reflect ***)
   121 (*** theorems about bt_reflect ***)
   131 
   122 
   132 val prems = goal BT_Fn.thy
   123 val prems = goal BT_Fn.thy
   133     "t: bt(A) ==> bt_reflect(bt_reflect(t))=t";
   124     "t: bt(A) ==> bt_reflect(bt_reflect(t))=t";
   134 by (bt_ind_tac "t" prems 1);
   125 by (bt_ind_tac "t" prems 1);
   135 by (ALLGOALS (ASM_SIMP_TAC bt_ss));
   126 by (ALLGOALS (asm_simp_tac bt_ss));
   136 val bt_reflect_bt_reflect_ident = result();
   127 val bt_reflect_bt_reflect_ident = result();
   137 
   128 
   138 
   129