Infinitely branching trees.
authorberghofe
Fri Jul 16 14:03:03 1999 +0200 (1999-07-16)
changeset 7018ae18bb3075c3
parent 7017 e4e64a0b0b6b
child 7019 71f2155cdd85
Infinitely branching trees.
src/HOL/Induct/Tree.ML
src/HOL/Induct/Tree.thy
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/HOL/Induct/Tree.ML	Fri Jul 16 14:03:03 1999 +0200
     1.3 @@ -0,0 +1,20 @@
     1.4 +(*  Title:      HOL/Induct/Tree.ML
     1.5 +    ID:         $Id$
     1.6 +    Author:     Stefan Berghofer,  TU Muenchen
     1.7 +    Copyright   1999  TU Muenchen
     1.8 +
     1.9 +Infinitely branching trees
    1.10 +*)
    1.11 +
    1.12 +Goal "map_tree g (map_tree f t) = map_tree (g o f) t";
    1.13 +by (induct_tac "t" 1);
    1.14 +by (ALLGOALS Asm_simp_tac);
    1.15 +qed "tree_map_compose";
    1.16 +
    1.17 +val prems = Goal "(!!x. P x ==> Q (f x)) ==>  \
    1.18 +   \    exists_tree P ts --> exists_tree Q (map_tree f ts)";
    1.19 +by (induct_tac "ts" 1);
    1.20 +by (ALLGOALS (asm_simp_tac (simpset() addsimps prems)));
    1.21 +by (Fast_tac 1);
    1.22 +qed "exists_map";
    1.23 +
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/HOL/Induct/Tree.thy	Fri Jul 16 14:03:03 1999 +0200
     2.3 @@ -0,0 +1,27 @@
     2.4 +(*  Title:      HOL/Induct/Tree.thy
     2.5 +    ID:         $Id$
     2.6 +    Author:     Stefan Berghofer,  TU Muenchen
     2.7 +    Copyright   1999  TU Muenchen
     2.8 +
     2.9 +Infinitely branching trees
    2.10 +*)
    2.11 +
    2.12 +Tree = Main +
    2.13 +
    2.14 +datatype 'a tree = Atom 'a | Branch "nat => 'a tree"
    2.15 +
    2.16 +consts
    2.17 +  map_tree :: "('a => 'b) => 'a tree => 'b tree"
    2.18 +
    2.19 +primrec
    2.20 +  "map_tree f (Atom a) = Atom (f a)"
    2.21 +  "map_tree f (Branch ts) = Branch (%x. map_tree f (ts x))"
    2.22 +
    2.23 +consts
    2.24 +  exists_tree :: "('a => bool) => 'a tree => bool"
    2.25 +
    2.26 +primrec
    2.27 +  "exists_tree P (Atom a) = P a"
    2.28 +  "exists_tree P (Branch ts) = (? x. exists_tree P (ts x))"
    2.29 +
    2.30 +end