equal
deleted
inserted
replaced
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 (*<*) |