author | lcp |
Thu, 28 Oct 1993 11:32:37 +0100 | |
changeset 85 | 914270f33f2d |
parent 71 | 729fe026c5f3 |
child 120 | 09287f26bfb8 |
permissions | -rw-r--r-- |
0 | 1 |
(* Title: ZF/ex/llist.ML |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1993 University of Cambridge |
|
5 |
||
6 |
Co-Datatype definition of Lazy Lists |
|
7 |
*) |
|
8 |
||
9 |
structure LList = Co_Datatype_Fun |
|
10 |
(val thy = QUniv.thy; |
|
11 |
val rec_specs = |
|
12 |
[("llist", "quniv(A)", |
|
13 |
[(["LNil"], "i"), |
|
14 |
(["LCons"], "[i,i]=>i")])]; |
|
15 |
val rec_styp = "i=>i"; |
|
16 |
val ext = None |
|
17 |
val sintrs = |
|
18 |
["LNil : llist(A)", |
|
19 |
"[| a: A; l: llist(A) |] ==> LCons(a,l) : llist(A)"]; |
|
20 |
val monos = []; |
|
71
729fe026c5f3
sample datatype defs now use datatype_intrs, datatype_elims
lcp
parents:
34
diff
changeset
|
21 |
val type_intrs = co_datatype_intrs |
85 | 22 |
val type_elims = co_datatype_elims); |
0 | 23 |
|
24 |
val [LNilI, LConsI] = LList.intrs; |
|
25 |
||
26 |
(*An elimination rule, for type-checking*) |
|
27 |
val LConsE = LList.mk_cases LList.con_defs "LCons(a,l) : llist(A)"; |
|
28 |
||
29 |
(*Proving freeness results*) |
|
30 |
val LCons_iff = LList.mk_free "LCons(a,l)=LCons(a',l') <-> a=a' & l=l'"; |
|
31 |
val LNil_LCons_iff = LList.mk_free "~ LNil=LCons(a,l)"; |
|
32 |
||
33 |
(*** Lemmas to justify using "llist" in other recursive type definitions ***) |
|
34 |
||
35 |
goalw LList.thy LList.defs "!!A B. A<=B ==> llist(A) <= llist(B)"; |
|
36 |
by (rtac gfp_mono 1); |
|
37 |
by (REPEAT (rtac LList.bnd_mono 1)); |
|
38 |
by (REPEAT (ares_tac (quniv_mono::basic_monos) 1)); |
|
39 |
val llist_mono = result(); |
|
40 |
||
41 |
(** Closure of quniv(A) under llist -- why so complex? Its a gfp... **) |
|
42 |
||
43 |
val in_quniv_rls = |
|
44 |
[Transset_quniv, QPair_Int_quniv_in_quniv, Int_Vfrom_0_in_quniv, |
|
45 |
zero_Int_in_quniv, one_Int_in_quniv, |
|
46 |
QPair_Int_Vfrom_succ_in_quniv, QPair_Int_Vfrom_in_quniv]; |
|
47 |
||
48 |
val quniv_cs = ZF_cs addSIs in_quniv_rls |
|
71
729fe026c5f3
sample datatype defs now use datatype_intrs, datatype_elims
lcp
parents:
34
diff
changeset
|
49 |
addIs (Int_quniv_in_quniv::co_datatype_intrs); |
0 | 50 |
|
51 |
(*Keep unfolding the lazy list until the induction hypothesis applies*) |
|
52 |
goal LList.thy |
|
53 |
"!!i. i : nat ==> \ |
|
54 |
\ ALL l: llist(quniv(A)). l Int Vfrom(quniv(A), i) : quniv(A)"; |
|
16
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
55 |
by (etac complete_induct 1); |
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
56 |
by (rtac ballI 1); |
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
57 |
by (etac LList.elim 1); |
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
58 |
by (rewrite_goals_tac ([QInl_def,QInr_def]@LList.con_defs)); |
0 | 59 |
by (fast_tac quniv_cs 1); |
60 |
by (etac natE 1 THEN REPEAT_FIRST hyp_subst_tac); |
|
61 |
by (fast_tac quniv_cs 1); |
|
62 |
by (fast_tac quniv_cs 1); |
|
63 |
val llist_quniv_lemma = result(); |
|
64 |
||
65 |
goal LList.thy "llist(quniv(A)) <= quniv(A)"; |
|
16
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
66 |
by (rtac subsetI 1); |
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
67 |
by (rtac quniv_Int_Vfrom 1); |
0b033d50ca1c
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
7
diff
changeset
|
68 |
by (etac (LList.dom_subset RS subsetD) 1); |
0 | 69 |
by (REPEAT (ares_tac [llist_quniv_lemma RS bspec] 1)); |
70 |
val llist_quniv = result(); |
|
71 |
||
72 |
val llist_subset_quniv = standard |
|
73 |
(llist_mono RS (llist_quniv RSN (2,subset_trans))); |
|
74 |
||
34
747f1aad03cf
changed filenames to lower case name of theory the file contains
clasohm
parents:
16
diff
changeset
|
75 |
(* Definition and use of LList_Eq has been moved to llist_eq.ML to allow |
747f1aad03cf
changed filenames to lower case name of theory the file contains
clasohm
parents:
16
diff
changeset
|
76 |
automatic association between theory name and filename. *) |