19 "{p. EX x y.p=<x,y> & (EX l:Lists(A).x=map(f o g,l) & y=map(f,map(g,l)))}" 1); |
19 "{p. EX x y.p=<x,y> & (EX l:Lists(A).x=map(f o g,l) & y=map(f,map(g,l)))}" 1); |
20 by (fast_tac (ccl_cs addSIs prems) 1); |
20 by (fast_tac (ccl_cs addSIs prems) 1); |
21 by (safe_tac type_cs); |
21 by (safe_tac type_cs); |
22 be (XH_to_E ListsXH) 1; |
22 be (XH_to_E ListsXH) 1; |
23 by (EQgen_tac list_ss [] 1); |
23 by (EQgen_tac list_ss [] 1); |
24 by (SIMP_TAC list_ss 1); |
24 by (simp_tac list_ss 1); |
25 by (fast_tac ccl_cs 1); |
25 by (fast_tac ccl_cs 1); |
26 val map_comp = result(); |
26 val map_comp = result(); |
27 |
27 |
28 (*** Mapping the identity function leaves a list unchanged ***) |
28 (*** Mapping the identity function leaves a list unchanged ***) |
29 |
29 |
85 (* fun iter1(f,a) = a.iter1(f,f(a)) *) |
85 (* fun iter1(f,a) = a.iter1(f,f(a)) *) |
86 (* fun iter2(f,a) = a.map(f,iter2(f,a)) *) |
86 (* fun iter2(f,a) = a.map(f,iter2(f,a)) *) |
87 |
87 |
88 goalw Stream.thy [iter1_def] "iter1(f,a) = a.iter1(f,f(a))"; |
88 goalw Stream.thy [iter1_def] "iter1(f,a) = a.iter1(f,f(a))"; |
89 br (letrecB RS trans) 1; |
89 br (letrecB RS trans) 1; |
90 by (SIMP_TAC term_ss 1); |
90 by (simp_tac term_ss 1); |
91 val iter1B = result(); |
91 val iter1B = result(); |
92 |
92 |
93 goalw Stream.thy [iter2_def] "iter2(f,a) = a . map(f,iter2(f,a))"; |
93 goalw Stream.thy [iter2_def] "iter2(f,a) = a . map(f,iter2(f,a))"; |
94 br (letrecB RS trans) 1; |
94 br (letrecB RS trans) 1; |
95 br refl 1; |
95 br refl 1; |
96 val iter2B = result(); |
96 val iter2B = result(); |
97 |
97 |
98 val [prem] =goal Stream.thy |
98 val [prem] =goal Stream.thy |
99 "n:Nat ==> map(f) ^ n ` iter2(f,a) = f ^ n ` a . map(f) ^ n ` map(f,iter2(f,a))"; |
99 "n:Nat ==> map(f) ^ n ` iter2(f,a) = f ^ n ` a . map(f) ^ n ` map(f,iter2(f,a))"; |
100 br (iter2B RS ssubst) 1;back();back(); |
100 br (iter2B RS ssubst) 1;back();back(); |
101 by (SIMP_TAC (list_ss addrews [prem RS nmapBcons]) 1); |
101 by (simp_tac (list_ss addsimps [prem RS nmapBcons]) 1); |
102 val iter2Blemma = result(); |
102 val iter2Blemma = result(); |
103 |
103 |
104 goal Stream.thy "iter1(f,a) = iter2(f,a)"; |
104 goal Stream.thy "iter1(f,a) = iter2(f,a)"; |
105 by (eq_coinduct3_tac |
105 by (eq_coinduct3_tac |
106 "{p. EX x y.p=<x,y> & (EX n:Nat.x=iter1(f,f^n`a) & y=map(f)^n`iter2(f,a))}" 1); |
106 "{p. EX x y.p=<x,y> & (EX n:Nat.x=iter1(f,f^n`a) & y=map(f)^n`iter2(f,a))}" |
107 by (fast_tac (type_cs addSIs [napplyBzero RS sym,napplyBzero RS sym RS arg_cong]) 1); |
107 1); |
|
108 by (fast_tac (type_cs addSIs [napplyBzero RS sym, |
|
109 napplyBzero RS sym RS arg_cong]) 1); |
108 by (EQgen_tac list_ss [iter1B,iter2Blemma] 1); |
110 by (EQgen_tac list_ss [iter1B,iter2Blemma] 1); |
|
111 by (assume_tac 1); (*should EQgen_tac call asm_simp_tac?*) |
109 by (rtac (napply_f RS ssubst) 1 THEN atac 1); |
112 by (rtac (napply_f RS ssubst) 1 THEN atac 1); |
110 by (res_inst_tac [("f1","f")] (napplyBsucc RS subst) 1); |
113 by (res_inst_tac [("f1","f")] (napplyBsucc RS subst) 1); |
111 by (fast_tac type_cs 1); |
114 by (fast_tac type_cs 1); |
112 val iter1_iter2_eq = result(); |
115 val iter1_iter2_eq = result(); |