doc-src/TutorialI/Misc/Tree.thy
changeset 10795 9e888d60d3e5
parent 9792 bbefb6ce5cb2
child 11456 7eb63f63e6c6
equal deleted inserted replaced
10794:65d18005d802 10795:9e888d60d3e5
     6 Define the datatype of binary trees
     6 Define the datatype of binary trees
     7 *}
     7 *}
     8 
     8 
     9 datatype 'a tree = Tip | Node "'a tree" 'a "'a tree";(*<*)
     9 datatype 'a tree = Tip | Node "'a tree" 'a "'a tree";(*<*)
    10 
    10 
    11 consts mirror :: "'a tree \\<Rightarrow> 'a tree";
    11 consts mirror :: "'a tree \<Rightarrow> 'a tree";
    12 primrec
    12 primrec
    13 "mirror Tip = Tip"
    13 "mirror Tip = Tip"
    14 "mirror (Node l x r) = Node (mirror r) x (mirror l)";(*>*)
    14 "mirror (Node l x r) = Node (mirror r) x (mirror l)";(*>*)
    15 
    15 
    16 text{*\noindent
    16 text{*\noindent
    17 and a function @{term"mirror"} that mirrors a binary tree
    17 and a function @{term"mirror"} that mirrors a binary tree
    18 by swapping subtrees (recursively). Prove
    18 by swapping subtrees recursively. Prove
    19 *}
    19 *}
    20 
    20 
    21 lemma mirror_mirror: "mirror(mirror t) = t";
    21 lemma mirror_mirror: "mirror(mirror t) = t";
    22 (*<*)
    22 (*<*)
    23 apply(induct_tac t);
    23 apply(induct_tac t);