src/HOLCF/ex/Stream.ML
changeset 11355 778c369559d9
parent 11348 e08a0855af67
child 11495 3621dea6113e
equal deleted inserted replaced
11354:9b80fe19407f 11355:778c369559d9
   382 
   382 
   383 Goalw [slen_def, stream.finite_def] "#\\<bottom> = 0";
   383 Goalw [slen_def, stream.finite_def] "#\\<bottom> = 0";
   384 by (Simp_tac 1);
   384 by (Simp_tac 1);
   385 by (stac Least_equality 1);
   385 by (stac Least_equality 1);
   386 by    Auto_tac;
   386 by    Auto_tac;
   387 by (simp_tac(simpset() addsimps [Fin_0]) 1);
   387 by (simp_tac(simpset() addsimps [thm "Fin_0"]) 1);
   388 qed "slen_empty";
   388 qed "slen_empty";
   389 
   389 
   390 Goalw [slen_def] "x ~= \\<bottom> ==> #(x&&xs) = iSuc (#xs)";
   390 Goalw [slen_def] "x ~= \\<bottom> ==> #(x&&xs) = iSuc (#xs)";
   391 by (res_inst_tac [("Q1","stream_finite (x && xs)")] (split_if RS iffD2) 1);
   391 by (res_inst_tac [("Q1","stream_finite (x && xs)")] (split_if RS iffD2) 1);
   392 by Safe_tac;
   392 by Safe_tac;
   393 by (rtac (split_if RS iffD2) 2);
   393 by (rtac (split_if RS iffD2) 2);
   394 by  Safe_tac;
   394 by  Safe_tac;
   395 by   (fast_tac (claset() addIs [stream_finite_lemma1]) 2);
   395 by   (fast_tac (claset() addIs [stream_finite_lemma1]) 2);
   396 by  (rtac (iSuc_Infty RS sym) 2);
   396 by  (rtac (thm "iSuc_Infty" RS sym) 2);
   397 by (rtac (split_if RS iffD2) 1);
   397 by (rtac (split_if RS iffD2) 1);
   398 by (Simp_tac 1);
   398 by (Simp_tac 1);
   399 by Safe_tac;
   399 by Safe_tac;
   400 by  (eatac stream_finite_lemma2 1 2);
   400 by  (eatac stream_finite_lemma2 1 2);
   401 by (rewtac stream.finite_def);
   401 by (rewtac stream.finite_def);
   407 
   407 
   408 Addsimps [slen_empty, slen_scons];
   408 Addsimps [slen_empty, slen_scons];
   409 
   409 
   410 Goal "#x < Fin 1 = (x = UU)";
   410 Goal "#x < Fin 1 = (x = UU)";
   411 by (stream_case_tac "x" 1);
   411 by (stream_case_tac "x" 1);
   412 by (auto_tac (claset(), simpset() delsimps [iSuc_Fin] addsimps
   412 by (auto_tac (claset(), simpset() delsimps [thm "iSuc_Fin"] addsimps
   413  [Fin_0, iSuc_Fin RS sym,i0_iless_iSuc, iSuc_mono]));
   413  [thm "Fin_0", thm "iSuc_Fin" RS sym, thm "i0_iless_iSuc", thm "iSuc_mono"]));
   414 qed "slen_less_1_eq";
   414 qed "slen_less_1_eq";
   415 
   415 
   416 Goal "(#x = 0) = (x = \\<bottom>)";
   416 Goal "(#x = 0) = (x = \\<bottom>)";
   417 by Auto_tac;
   417 by Auto_tac;
   418 by (stream_case_tac "x" 1);
   418 by (stream_case_tac "x" 1);
   420 by Auto_tac;
   420 by Auto_tac;
   421 qed "slen_empty_eq";
   421 qed "slen_empty_eq";
   422 
   422 
   423 Goal "Fin (Suc n) < #x = (? a y. x = a && y &  a ~= \\<bottom> &  Fin n < #y)";
   423 Goal "Fin (Suc n) < #x = (? a y. x = a && y &  a ~= \\<bottom> &  Fin n < #y)";
   424 by (stream_case_tac "x" 1);
   424 by (stream_case_tac "x" 1);
   425 by (auto_tac (claset(), simpset() delsimps [iSuc_Fin] addsimps
   425 by (auto_tac (claset(), simpset() delsimps [thm "iSuc_Fin"] addsimps
   426                 [iSuc_Fin RS sym, iSuc_mono]));
   426                 [thm "iSuc_Fin" RS sym, thm "iSuc_mono"]));
   427 by  (dtac sym 1);
   427 by  (dtac sym 1);
   428 by  (rotate_tac 2 2);
   428 by  (rotate_tac 2 2);
   429 by  Auto_tac;
   429 by  Auto_tac;
   430 qed "slen_scons_eq";
   430 qed "slen_scons_eq";
   431 
   431 
   436 qed_spec_mp "slen_iSuc";
   436 qed_spec_mp "slen_iSuc";
   437 
   437 
   438 
   438 
   439 Goal 
   439 Goal 
   440 "#x < Fin (Suc (Suc n)) = (!a y. x ~= a && y |  a = \\<bottom> |  #y < Fin (Suc n))";
   440 "#x < Fin (Suc (Suc n)) = (!a y. x ~= a && y |  a = \\<bottom> |  #y < Fin (Suc n))";
   441 by (stac (iSuc_Fin RS sym) 1);
   441 by (stac (thm "iSuc_Fin" RS sym) 1);
   442 by (stac (iSuc_Fin RS sym) 1);
   442 by (stac (thm "iSuc_Fin" RS sym) 1);
   443 by (safe_tac HOL_cs);
   443 by (safe_tac HOL_cs);
   444 by  (rotate_tac ~1 1);
   444 by  (rotate_tac ~1 1);
   445 by  (asm_full_simp_tac (HOL_ss addsimps [slen_scons, iSuc_mono]) 1);
   445 by  (asm_full_simp_tac (HOL_ss addsimps [slen_scons, thm "iSuc_mono"]) 1);
   446 by  (Asm_full_simp_tac 1);
   446 by  (Asm_full_simp_tac 1);
   447 by (stream_case_tac "x" 1);
   447 by (stream_case_tac "x" 1);
   448 by ( simp_tac (HOL_ss addsimps [slen_empty, i0_iless_iSuc]) 1);
   448 by ( simp_tac (HOL_ss addsimps [slen_empty, thm "i0_iless_iSuc"]) 1);
   449 by (asm_simp_tac (HOL_ss addsimps [slen_scons, iSuc_mono]) 1);
   449 by (asm_simp_tac (HOL_ss addsimps [slen_scons, thm "iSuc_mono"]) 1);
   450 by (etac allE 1);
   450 by (etac allE 1);
   451 by (etac allE 1);
   451 by (etac allE 1);
   452 by (safe_tac HOL_cs);
   452 by (safe_tac HOL_cs);
   453 by (  contr_tac 2);
   453 by (  contr_tac 2);
   454 by ( fast_tac HOL_cs 1);
   454 by ( fast_tac HOL_cs 1);
   455 by (Asm_full_simp_tac 1);
   455 by (Asm_full_simp_tac 1);
   456 qed "slen_scons_eq_rev";
   456 qed "slen_scons_eq_rev";
   457 
   457 
   458 Goal "!x. Fin n < #x = (stream_take n\\<cdot>x ~= x)";
   458 Goal "!x. Fin n < #x = (stream_take n\\<cdot>x ~= x)";
   459 by (nat_ind_tac "n" 1);
   459 by (nat_ind_tac "n" 1);
   460 by  (simp_tac(simpset() addsimps [slen_empty_eq, Fin_0]) 1);
   460 by  (simp_tac(simpset() addsimps [slen_empty_eq, thm "Fin_0"]) 1);
   461 by  (Fast_tac 1);
   461 by  (Fast_tac 1);
   462 by (rtac allI 1);
   462 by (rtac allI 1);
   463 by (asm_simp_tac (simpset() addsimps [slen_scons_eq]) 1);
   463 by (asm_simp_tac (simpset() addsimps [slen_scons_eq]) 1);
   464 by (etac thin_rl 1);
   464 by (etac thin_rl 1);
   465 by (safe_tac HOL_cs);
   465 by (safe_tac HOL_cs);
   467 by (stream_case_tac "x" 1);
   467 by (stream_case_tac "x" 1);
   468 by (rotate_tac ~1 2);
   468 by (rotate_tac ~1 2);
   469 by Auto_tac;
   469 by Auto_tac;
   470 qed_spec_mp "slen_take_eq";
   470 qed_spec_mp "slen_take_eq";
   471 
   471 
   472 Goalw [ile_def] "#x <= Fin n = (stream_take n\\<cdot>x = x)";
   472 Goalw [thm "ile_def"] "#x <= Fin n = (stream_take n\\<cdot>x = x)";
   473 by (simp_tac (simpset() addsimps [slen_take_eq]) 1);
   473 by (simp_tac (simpset() addsimps [slen_take_eq]) 1);
   474 qed "slen_take_eq_rev";
   474 qed "slen_take_eq_rev";
   475 
   475 
   476 Goal "#x = Fin n ==> stream_take n\\<cdot>x = x";
   476 Goal "#x = Fin n ==> stream_take n\\<cdot>x = x";
   477 by (asm_simp_tac (simpset() addsimps [slen_take_eq_rev RS sym]) 1);
   477 by (asm_simp_tac (simpset() addsimps [slen_take_eq_rev RS sym]) 1);
   478 qed "slen_take_lemma1";
   478 qed "slen_take_lemma1";
   479 
   479 
   480 Goal "!x. ~stream_finite x --> #(stream_take i\\<cdot>x) = Fin i";
   480 Goal "!x. ~stream_finite x --> #(stream_take i\\<cdot>x) = Fin i";
   481 by (nat_ind_tac "i" 1);
   481 by (nat_ind_tac "i" 1);
   482 by  (simp_tac(simpset() addsimps [Fin_0]) 1);
   482 by  (simp_tac(simpset() addsimps [thm "Fin_0"]) 1);
   483 by (rtac allI 1);
   483 by (rtac allI 1);
   484 by (stream_case_tac "x" 1);
   484 by (stream_case_tac "x" 1);
   485 by  (auto_tac (claset()addSIs [stream_finite_lemma1], simpset() delsimps [iSuc_Fin] addsimps [iSuc_Fin RS sym]));
   485 by  (auto_tac (claset()addSIs [stream_finite_lemma1], simpset() delsimps [thm "iSuc_Fin"] addsimps [thm "iSuc_Fin" RS sym]));
   486 by (force_tac (claset(), simpset() addsimps [stream.finite_def]) 1);
   486 by (force_tac (claset(), simpset() addsimps [stream.finite_def]) 1);
   487 qed_spec_mp "slen_take_lemma2";
   487 qed_spec_mp "slen_take_lemma2";
   488 
   488 
   489 Goal "stream_finite x = (#x ~= Infty)";
   489 Goal "stream_finite x = (#x ~= Infty)";
   490 by (rtac iffI 1);
   490 by (rtac iffI 1);
   491 by  (etac stream_finite_ind 1);
   491 by  (etac stream_finite_ind 1);
   492 by   (Simp_tac 1);
   492 by   (Simp_tac 1);
   493 by  (etac (slen_scons RS ssubst) 1);
   493 by  (etac (slen_scons RS ssubst) 1);
   494 by  (stac (iSuc_Infty RS sym) 1);
   494 by  (stac (thm "iSuc_Infty" RS sym) 1);
   495 by  (etac contrapos_nn 1);
   495 by  (etac contrapos_nn 1);
   496 by  (etac (iSuc_inject RS iffD1) 1);
   496 by  (etac (thm "iSuc_inject" RS iffD1) 1);
   497 by (case_tac "#x" 1);
   497 by (case_tac "#x" 1);
   498 by (auto_tac (claset()addSDs [slen_take_lemma1],
   498 by (auto_tac (claset()addSDs [slen_take_lemma1],
   499         simpset() addsimps [stream.finite_def]));
   499         simpset() addsimps [stream.finite_def]));
   500 qed "slen_infinite";
   500 qed "slen_infinite";
   501 
   501 
   508 by  (atac 2);
   508 by  (atac 2);
   509 by (etac (stream_finite_ind) 1);
   509 by (etac (stream_finite_ind) 1);
   510 by  (Simp_tac 1);
   510 by  (Simp_tac 1);
   511 by (rtac allI 1);
   511 by (rtac allI 1);
   512 by (stream_case_tac "x" 1);
   512 by (stream_case_tac "x" 1);
   513 by  (asm_simp_tac (HOL_ss addsimps [slen_empty, i0_lb]) 1);
   513 by  (asm_simp_tac (HOL_ss addsimps [slen_empty, thm "i0_lb"]) 1);
   514 by (asm_simp_tac (HOL_ss addsimps [slen_scons]) 1);
   514 by (asm_simp_tac (HOL_ss addsimps [slen_scons]) 1);
   515 by (fast_tac(claset() addSIs [iSuc_ile_mono RS iffD2] addSDs stream.inverts) 1);
   515 by (fast_tac(claset() addSIs [thm "iSuc_ile_mono" RS iffD2] addSDs stream.inverts) 1);
   516 qed "slen_mono";
   516 qed "slen_mono";
   517 
   517 
   518 Goal "!(x::'a::flat stream) y. Fin n <= #x --> x << y --> \
   518 Goal "!(x::'a::flat stream) y. Fin n <= #x --> x << y --> \
   519 \ stream_take n\\<cdot>x = stream_take n\\<cdot>y";
   519 \ stream_take n\\<cdot>x = stream_take n\\<cdot>y";
   520 by (nat_ind_tac "n" 1);
   520 by (nat_ind_tac "n" 1);
   521 by ( simp_tac(simpset() addsimps [slen_empty_eq]) 1);
   521 by ( simp_tac(simpset() addsimps [slen_empty_eq]) 1);
   522 by (strip_tac 1);
   522 by (strip_tac 1);
   523 by (stream_case_tac "x" 1);
   523 by (stream_case_tac "x" 1);
   524 by  (asm_full_simp_tac (HOL_ss addsimps [slen_empty, 
   524 by  (asm_full_simp_tac (HOL_ss addsimps [slen_empty, 
   525               iSuc_Fin RS sym, not_iSuc_ilei0]) 1);
   525               thm "iSuc_Fin" RS sym, thm "not_iSuc_ilei0"]) 1);
   526 by (fatac stream_prefix 1 1);
   526 by (fatac stream_prefix 1 1);
   527 by (safe_tac (claset() addSDs [stream_flat_prefix]));
   527 by (safe_tac (claset() addSDs [stream_flat_prefix]));
   528 by (Simp_tac 1);
   528 by (Simp_tac 1);
   529 by (rtac cfun_arg_cong 1);
   529 by (rtac cfun_arg_cong 1);
   530 by (rotate_tac 3 1);
   530 by (rotate_tac 3 1);
   531 by (asm_full_simp_tac (simpset() delsimps [iSuc_Fin] addsimps 
   531 by (asm_full_simp_tac (simpset() delsimps [thm "iSuc_Fin"] addsimps 
   532         [iSuc_Fin RS sym, iSuc_ile_mono]) 1);
   532         [thm "iSuc_Fin" RS sym, thm "iSuc_ile_mono"]) 1);
   533 qed_spec_mp "slen_take_lemma3";
   533 qed_spec_mp "slen_take_lemma3";
   534 
   534 
   535 Goal "stream_finite t ==> \
   535 Goal "stream_finite t ==> \
   536 \!s. #(s::'a::flat stream) = #t &  s << t --> s = t";
   536 \!s. #(s::'a::flat stream) = #t &  s << t --> s = t";
   537 by (etac stream_finite_ind 1);
   537 by (etac stream_finite_ind 1);
   546 by (etac mp 1);
   546 by (etac mp 1);
   547 by (Asm_full_simp_tac 1);
   547 by (Asm_full_simp_tac 1);
   548 qed "slen_strict_mono_lemma";
   548 qed "slen_strict_mono_lemma";
   549 
   549 
   550 Goal "[|stream_finite t; s ~= t; s << (t::'a::flat stream) |] ==> #s < #t";
   550 Goal "[|stream_finite t; s ~= t; s << (t::'a::flat stream) |] ==> #s < #t";
   551 by (rtac ilessI1 1);
   551 by (rtac (thm "ilessI1") 1);
   552 by  (etac slen_mono 1);
   552 by  (etac slen_mono 1);
   553 by (dtac slen_strict_mono_lemma 1);
   553 by (dtac slen_strict_mono_lemma 1);
   554 by (Fast_tac 1);
   554 by (Fast_tac 1);
   555 qed "slen_strict_mono";
   555 qed "slen_strict_mono";
   556 
   556 
   557 Goal "!x. Fin (i + j) <= #x --> Fin j <= #(iterate i rt x)";
   557 Goal "!x. Fin (i + j) <= #x --> Fin j <= #(iterate i rt x)";
   558 by (nat_ind_tac "i" 1);
   558 by (nat_ind_tac "i" 1);
   559 by  (Simp_tac 1);
   559 by  (Simp_tac 1);
   560 by (strip_tac 1);
   560 by (strip_tac 1);
   561 by (stream_case_tac "x" 1);
   561 by (stream_case_tac "x" 1);
   562 by  (asm_full_simp_tac (simpset() delsimps [iSuc_Fin] 
   562 by  (asm_full_simp_tac (simpset() delsimps [thm "iSuc_Fin"] 
   563              addsimps [iSuc_Fin RS sym]) 1);
   563              addsimps [thm "iSuc_Fin" RS sym]) 1);
   564 by (stac iterate_Suc2 1);
   564 by (stac iterate_Suc2 1);
   565 by (rotate_tac 2 1);
   565 by (rotate_tac 2 1);
   566 by (asm_full_simp_tac  (simpset() delsimps [iSuc_Fin] 
   566 by (asm_full_simp_tac  (simpset() delsimps [thm "iSuc_Fin"] 
   567     addsimps [iSuc_Fin RS sym, iSuc_ile_mono]) 1);
   567     addsimps [thm "iSuc_Fin" RS sym, thm "iSuc_ile_mono"]) 1);
   568 qed_spec_mp "slen_rt_mult";
   568 qed_spec_mp "slen_rt_mult";
   569 
   569 
   570 
   570 
   571 (* ------------------------------------------------------------------------- *)
   571 (* ------------------------------------------------------------------------- *)
   572 
   572