src/Doc/Tutorial/Misc/Tree.thy
changeset 69597 ff784d5a5bfb
parent 67406 23307fd33906
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    11 primrec mirror :: "'a tree \<Rightarrow> 'a tree" where
    11 primrec mirror :: "'a tree \<Rightarrow> 'a tree" where
    12 "mirror Tip = Tip" |
    12 "mirror Tip = Tip" |
    13 "mirror (Node l x r) = Node (mirror r) x (mirror l)"(*>*)
    13 "mirror (Node l x r) = Node (mirror r) x (mirror l)"(*>*)
    14 
    14 
    15 text\<open>\noindent
    15 text\<open>\noindent
    16 Define a function @{term"mirror"} that mirrors a binary tree
    16 Define a function \<^term>\<open>mirror\<close> that mirrors a binary tree
    17 by swapping subtrees recursively. Prove
    17 by swapping subtrees recursively. Prove
    18 \<close>
    18 \<close>
    19 
    19 
    20 lemma mirror_mirror: "mirror(mirror t) = t"
    20 lemma mirror_mirror: "mirror(mirror t) = t"
    21 (*<*)
    21 (*<*)
    26 "flatten Tip = []" |
    26 "flatten Tip = []" |
    27 "flatten (Node l x r) = flatten l @ [x] @ flatten r"
    27 "flatten (Node l x r) = flatten l @ [x] @ flatten r"
    28 (*>*)
    28 (*>*)
    29 
    29 
    30 text\<open>\noindent
    30 text\<open>\noindent
    31 Define a function @{term"flatten"} that flattens a tree into a list
    31 Define a function \<^term>\<open>flatten\<close> that flattens a tree into a list
    32 by traversing it in infix order. Prove
    32 by traversing it in infix order. Prove
    33 \<close>
    33 \<close>
    34 
    34 
    35 lemma "flatten(mirror t) = rev(flatten t)"
    35 lemma "flatten(mirror t) = rev(flatten t)"
    36 (*<*)
    36 (*<*)