src/HOL/Codatatype/Examples/Misc_Data.thy
author blanchet
Fri Sep 21 16:34:40 2012 +0200 (2012-09-21)
changeset 49509 163914705f8d
parent 49463 83ac281bcdc2
permissions -rw-r--r--
renamed top-level theory from "Codatatype" to "BNF"
blanchet@49509
     1
(*  Title:      HOL/BNF/Examples/Misc_Data.thy
blanchet@48975
     2
    Author:     Dmitriy Traytel, TU Muenchen
blanchet@48975
     3
    Author:     Andrei Popescu, TU Muenchen
blanchet@48975
     4
    Copyright   2012
blanchet@48975
     5
blanchet@48975
     6
Miscellaneous datatype declarations.
blanchet@48975
     7
*)
blanchet@48975
     8
blanchet@48975
     9
header {* Miscellaneous Datatype Declarations *}
blanchet@48975
    10
blanchet@48975
    11
theory Misc_Data
blanchet@49509
    12
imports "../BNF"
blanchet@48975
    13
begin
blanchet@48975
    14
blanchet@49157
    15
data simple = X1 | X2 | X3 | X4
blanchet@49157
    16
blanchet@49157
    17
data simple' = X1' unit | X2' unit | X3' unit | X4' unit
blanchet@48975
    18
blanchet@49157
    19
data 'a mylist = MyNil | MyCons 'a "'a mylist"
blanchet@48975
    20
blanchet@49157
    21
data ('b, 'c, 'd, 'e) some_passive =
blanchet@49157
    22
  SP1 "('b, 'c, 'd, 'e) some_passive" | SP2 'b | SP3 'c | SP4 'd | SP5 'e
blanchet@48975
    23
blanchet@49157
    24
data lambda =
blanchet@49157
    25
  Var string |
blanchet@49157
    26
  App lambda lambda |
blanchet@49157
    27
  Abs string lambda |
blanchet@49157
    28
  Let "(string \<times> lambda) fset" lambda
blanchet@48975
    29
blanchet@49157
    30
data 'a par_lambda =
blanchet@49157
    31
  PVar 'a |
blanchet@49157
    32
  PApp "'a par_lambda" "'a par_lambda" |
blanchet@49157
    33
  PAbs 'a "'a par_lambda" |
blanchet@49157
    34
  PLet "('a \<times> 'a par_lambda) fset" "'a par_lambda"
blanchet@48975
    35
blanchet@48975
    36
(*
blanchet@48975
    37
  ('a, 'b1, 'b2) F1 = 'a * 'b1 + 'a * 'b2
blanchet@48975
    38
  ('a, 'b1, 'b2) F2 = unit + 'b1 * 'b2
blanchet@48975
    39
*)
blanchet@48975
    40
blanchet@49157
    41
data 'a I1 = I11 'a "'a I1" | I12 'a "'a I2"
blanchet@49157
    42
 and 'a I2 = I21 | I22 "'a I1" "'a I2"
blanchet@48975
    43
blanchet@49157
    44
data 'a tree = TEmpty | TNode 'a "'a forest"
blanchet@49157
    45
 and 'a forest = FNil | FCons "'a tree" "'a forest"
blanchet@48975
    46
blanchet@49157
    47
data 'a tree' = TEmpty' | TNode' "'a branch" "'a branch"
blanchet@49157
    48
 and 'a branch = Branch 'a "'a tree'"
blanchet@48975
    49
blanchet@49157
    50
data ('a, 'b) exp = Term "('a, 'b) trm" | Sum "('a, 'b) trm" "('a, 'b) exp"
blanchet@49157
    51
 and ('a, 'b) trm = Factor "('a, 'b) factor" | Prod "('a, 'b) factor" "('a, 'b) trm"
blanchet@49157
    52
 and ('a, 'b) factor = C 'a | V 'b | Paren "('a, 'b) exp"
blanchet@48975
    53
blanchet@49157
    54
data ('a, 'b, 'c) some_killing =
blanchet@49157
    55
  SK "'a \<Rightarrow> 'b \<Rightarrow> ('a, 'b, 'c) some_killing + ('a, 'b, 'c) in_here"
blanchet@49157
    56
 and ('a, 'b, 'c) in_here =
blanchet@49157
    57
  IH1 'b 'a | IH2 'c
blanchet@48975
    58
blanchet@49219
    59
data 'b nofail1 = NF11 "'b nofail1" 'b | NF12 'b
blanchet@49157
    60
data 'b nofail2 = NF2 "('b nofail2 \<times> 'b \<times> 'b nofail2 \<times> 'b) list"
blanchet@49219
    61
data 'b nofail3 = NF3 'b "('b nofail3 \<times> 'b \<times> 'b nofail3 \<times> 'b) fset"
blanchet@49219
    62
data 'b nofail4 = NF4 "('b nofail4 \<times> ('b nofail4 \<times> 'b \<times> 'b nofail4 \<times> 'b) fset) list"
blanchet@48975
    63
blanchet@48975
    64
(*
blanchet@49219
    65
data 'b fail = F "'b fail" 'b "'b fail" "'b list"
blanchet@49219
    66
data 'b fail = F "'b fail" 'b "'b fail" 'b
blanchet@49219
    67
data 'b fail = F1 "'b fail" 'b | F2 "'b fail"
blanchet@49219
    68
data 'b fail = F "'b fail" 'b
blanchet@48975
    69
*)
blanchet@48975
    70
blanchet@49157
    71
data l1 = L1 "l2 list"
blanchet@49157
    72
 and l2 = L21 "l1 fset" | L22 l2
blanchet@48975
    73
blanchet@49157
    74
data kk1 = KK1 kk2
blanchet@49157
    75
 and kk2 = KK2 kk3
blanchet@49157
    76
 and kk3 = KK3 "kk1 list"
blanchet@48975
    77
blanchet@49157
    78
data t1 = T11 t3 | T12 t2
blanchet@49157
    79
 and t2 = T2 t1
blanchet@49157
    80
 and t3 = T3
blanchet@48975
    81
blanchet@49157
    82
data t1' = T11' t2' | T12' t3'
blanchet@49157
    83
 and t2' = T2' t1'
blanchet@49157
    84
 and t3' = T3'
blanchet@48975
    85
blanchet@48975
    86
(*
blanchet@49157
    87
data fail1 = F1 fail2
blanchet@49157
    88
 and fail2 = F2 fail3
blanchet@49157
    89
 and fail3 = F3 fail1
blanchet@48975
    90
blanchet@49157
    91
data fail1 = F1 "fail2 list" fail2
blanchet@49157
    92
 and fail2 = F2 "fail2 fset" fail3
blanchet@49157
    93
 and fail3 = F3 fail1
blanchet@48975
    94
blanchet@49157
    95
data fail1 = F1 "fail2 list" fail2
blanchet@49157
    96
 and fail2 = F2 "fail1 fset" fail1
blanchet@48975
    97
*)
blanchet@49157
    98
blanchet@49162
    99
(* SLOW
blanchet@49157
   100
data ('a, 'c) D1 = A1 "('a, 'c) D2" | B1 "'a list"
blanchet@49157
   101
 and ('a, 'c) D2 = A2 "('a, 'c) D3" | B2 "'c list"
blanchet@49157
   102
 and ('a, 'c) D3 = A3 "('a, 'c) D3" | B3 "('a, 'c) D4" | C3 "('a, 'c) D4" "('a, 'c) D5"
blanchet@49157
   103
 and ('a, 'c) D4 = A4 "('a, 'c) D5" | B4 "'a list list list"
blanchet@49157
   104
 and ('a, 'c) D5 = A5 "('a, 'c) D6"
blanchet@49157
   105
 and ('a, 'c) D6 = A6 "('a, 'c) D7"
blanchet@49157
   106
 and ('a, 'c) D7 = A7 "('a, 'c) D8"
blanchet@49157
   107
 and ('a, 'c) D8 = A8 "('a, 'c) D1 list"
blanchet@48975
   108
blanchet@48975
   109
(*time comparison*)
blanchet@49157
   110
datatype ('a, 'c) D1' = A1' "('a, 'c) D2'" | B1' "'a list"
blanchet@49157
   111
     and ('a, 'c) D2' = A2' "('a, 'c) D3'" | B2' "'c list"
blanchet@49157
   112
     and ('a, 'c) D3' = A3' "('a, 'c) D3'" | B3' "('a, 'c) D4'" | C3' "('a, 'c) D4'" "('a, 'c) D5'"
blanchet@49157
   113
     and ('a, 'c) D4' = A4' "('a, 'c) D5'" | B4' "'a list list list"
blanchet@49157
   114
     and ('a, 'c) D5' = A5' "('a, 'c) D6'"
blanchet@49157
   115
     and ('a, 'c) D6' = A6' "('a, 'c) D7'"
blanchet@49157
   116
     and ('a, 'c) D7' = A7' "('a, 'c) D8'"
blanchet@49157
   117
     and ('a, 'c) D8' = A8' "('a, 'c) D1' list"
blanchet@49162
   118
*)
blanchet@48975
   119
blanchet@48975
   120
(* fail:
blanchet@49157
   121
data tt1 = TT11 tt2 tt3 | TT12 tt2 tt4
blanchet@49157
   122
 and tt2 = TT2
blanchet@49157
   123
 and tt3 = TT3 tt4
blanchet@49157
   124
 and tt4 = TT4 tt1
blanchet@48975
   125
*)
blanchet@48975
   126
blanchet@49157
   127
data k1 = K11 k2 k3 | K12 k2 k4
blanchet@49157
   128
 and k2 = K2
blanchet@49157
   129
 and k3 = K3 k4
blanchet@49157
   130
 and k4 = K4
blanchet@48975
   131
blanchet@49157
   132
data tt1 = TT11 tt3 tt2 | TT12 tt2 tt4
blanchet@49157
   133
 and tt2 = TT2
blanchet@49157
   134
 and tt3 = TT3 tt1
blanchet@49157
   135
 and tt4 = TT4
blanchet@49157
   136
blanchet@49162
   137
(* SLOW
blanchet@49157
   138
data s1 = S11 s2 s3 s4 | S12 s3 | S13 s2 s6 | S14 s4 s2 | S15 s2 s2
blanchet@49157
   139
 and s2 = S21 s7 s5 | S22 s5 s4 s6
blanchet@49157
   140
 and s3 = S31 s1 s7 s2 | S32 s3 s3 | S33 s4 s5
blanchet@49157
   141
 and s4 = S4 s5
blanchet@49157
   142
 and s5 = S5
blanchet@49157
   143
 and s6 = S61 s6 | S62 s1 s2 | S63 s6
blanchet@49157
   144
 and s7 = S71 s8 | S72 s5
blanchet@49157
   145
 and s8 = S8 nat
blanchet@49162
   146
*)
blanchet@48975
   147
blanchet@49436
   148
data ('a, 'b) bar = Bar "'b \<Rightarrow> 'a"
blanchet@49436
   149
data ('a, 'b, 'c, 'd) foo = Foo "'d + 'b \<Rightarrow> 'c + 'a"
traytel@49185
   150
traytel@49185
   151
data 'a dead_foo = A
traytel@49185
   152
data ('a, 'b) use_dead_foo = Y "'a" "'b dead_foo"
traytel@49186
   153
blanchet@48975
   154
end