6 *) |
6 *) |
7 |
7 |
8 header {* Analogues of the Cartesian Product and Disjoint Sum for Datatypes *} |
8 header {* Analogues of the Cartesian Product and Disjoint Sum for Datatypes *} |
9 |
9 |
10 theory Datatype |
10 theory Datatype |
11 imports Nat Product_Type |
11 imports Product_Type Sum_Type Nat |
|
12 uses |
|
13 ("Tools/Datatype/datatype_rep_proofs.ML") |
|
14 ("Tools/inductive_realizer.ML") |
|
15 ("Tools/Datatype/datatype_realizer.ML") |
12 begin |
16 begin |
|
17 |
|
18 subsection {* The datatype universe *} |
13 |
19 |
14 typedef (Node) |
20 typedef (Node) |
15 ('a,'b) node = "{p. EX f x k. p = (f::nat=>'b+nat, x::'a+nat) & f k = Inr 0}" |
21 ('a,'b) node = "{p. EX f x k. p = (f::nat=>'b+nat, x::'a+nat) & f k = Inr 0}" |
16 --{*it is a subtype of @{text "(nat=>'b+nat) * ('a+nat)"}*} |
22 --{*it is a subtype of @{text "(nat=>'b+nat) * ('a+nat)"}*} |
17 by auto |
23 by auto |
511 |
517 |
512 text {* hides popular names *} |
518 text {* hides popular names *} |
513 hide (open) type node item |
519 hide (open) type node item |
514 hide (open) const Push Node Atom Leaf Numb Lim Split Case |
520 hide (open) const Push Node Atom Leaf Numb Lim Split Case |
515 |
521 |
516 |
522 use "Tools/Datatype/datatype_rep_proofs.ML" |
517 section {* Datatypes *} |
523 |
518 |
524 use "Tools/inductive_realizer.ML" |
519 subsection {* Representing sums *} |
525 setup InductiveRealizer.setup |
520 |
526 |
521 rep_datatype (sum) Inl Inr |
527 use "Tools/Datatype/datatype_realizer.ML" |
522 proof - |
528 setup DatatypeRealizer.setup |
523 fix P |
|
524 fix s :: "'a + 'b" |
|
525 assume x: "\<And>x\<Colon>'a. P (Inl x)" and y: "\<And>y\<Colon>'b. P (Inr y)" |
|
526 then show "P s" by (auto intro: sumE [of s]) |
|
527 qed simp_all |
|
528 |
|
529 lemma sum_case_KK[simp]: "sum_case (%x. a) (%x. a) = (%x. a)" |
|
530 by (rule ext) (simp split: sum.split) |
|
531 |
|
532 lemma surjective_sum: "sum_case (%x::'a. f (Inl x)) (%y::'b. f (Inr y)) s = f(s)" |
|
533 apply (rule_tac s = s in sumE) |
|
534 apply (erule ssubst) |
|
535 apply (rule sum.cases(1)) |
|
536 apply (erule ssubst) |
|
537 apply (rule sum.cases(2)) |
|
538 done |
|
539 |
|
540 lemma sum_case_weak_cong: "s = t ==> sum_case f g s = sum_case f g t" |
|
541 -- {* Prevents simplification of @{text f} and @{text g}: much faster. *} |
|
542 by simp |
|
543 |
|
544 lemma sum_case_inject: |
|
545 "sum_case f1 f2 = sum_case g1 g2 ==> (f1 = g1 ==> f2 = g2 ==> P) ==> P" |
|
546 proof - |
|
547 assume a: "sum_case f1 f2 = sum_case g1 g2" |
|
548 assume r: "f1 = g1 ==> f2 = g2 ==> P" |
|
549 show P |
|
550 apply (rule r) |
|
551 apply (rule ext) |
|
552 apply (cut_tac x = "Inl x" in a [THEN fun_cong], simp) |
|
553 apply (rule ext) |
|
554 apply (cut_tac x = "Inr x" in a [THEN fun_cong], simp) |
|
555 done |
|
556 qed |
|
557 |
|
558 constdefs |
|
559 Suml :: "('a => 'c) => 'a + 'b => 'c" |
|
560 "Suml == (%f. sum_case f undefined)" |
|
561 |
|
562 Sumr :: "('b => 'c) => 'a + 'b => 'c" |
|
563 "Sumr == sum_case undefined" |
|
564 |
|
565 lemma [code]: |
|
566 "Suml f (Inl x) = f x" |
|
567 by (simp add: Suml_def) |
|
568 |
|
569 lemma [code]: |
|
570 "Sumr f (Inr x) = f x" |
|
571 by (simp add: Sumr_def) |
|
572 |
|
573 lemma Suml_inject: "Suml f = Suml g ==> f = g" |
|
574 by (unfold Suml_def) (erule sum_case_inject) |
|
575 |
|
576 lemma Sumr_inject: "Sumr f = Sumr g ==> f = g" |
|
577 by (unfold Sumr_def) (erule sum_case_inject) |
|
578 |
|
579 primrec Projl :: "'a + 'b => 'a" |
|
580 where Projl_Inl: "Projl (Inl x) = x" |
|
581 |
|
582 primrec Projr :: "'a + 'b => 'b" |
|
583 where Projr_Inr: "Projr (Inr x) = x" |
|
584 |
|
585 hide (open) const Suml Sumr Projl Projr |
|
586 |
529 |
587 end |
530 end |