equal
deleted
inserted
replaced
1 (*<*) |
1 (*<*) |
2 theory Tree2 imports Tree begin |
2 theory Tree2 imports Tree begin |
3 (*>*) |
3 (*>*) |
4 |
4 |
5 text{*\noindent In Exercise~\ref{ex:Tree} we defined a function |
5 text\<open>\noindent In Exercise~\ref{ex:Tree} we defined a function |
6 @{term"flatten"} from trees to lists. The straightforward version of |
6 @{term"flatten"} from trees to lists. The straightforward version of |
7 @{term"flatten"} is based on @{text"@"} and is thus, like @{term"rev"}, |
7 @{term"flatten"} is based on @{text"@"} and is thus, like @{term"rev"}, |
8 quadratic. A linear time version of @{term"flatten"} again reqires an extra |
8 quadratic. A linear time version of @{term"flatten"} again reqires an extra |
9 argument, the accumulator. Define *} |
9 argument, the accumulator. Define\<close> |
10 (*<*)primrec(*>*)flatten2 :: "'a tree \<Rightarrow> 'a list \<Rightarrow> 'a list"(*<*)where |
10 (*<*)primrec(*>*)flatten2 :: "'a tree \<Rightarrow> 'a list \<Rightarrow> 'a list"(*<*)where |
11 "flatten2 Tip xs = xs" | |
11 "flatten2 Tip xs = xs" | |
12 "flatten2 (Node l x r) xs = flatten2 l (x#(flatten2 r xs))" |
12 "flatten2 (Node l x r) xs = flatten2 l (x#(flatten2 r xs))" |
13 (*>*) |
13 (*>*) |
14 |
14 |
15 text{*\noindent and prove*} |
15 text\<open>\noindent and prove\<close> |
16 (*<*) |
16 (*<*) |
17 lemma [simp]: "!xs. flatten2 t xs = flatten t @ xs" |
17 lemma [simp]: "!xs. flatten2 t xs = flatten t @ xs" |
18 apply(induct_tac t) |
18 apply(induct_tac t) |
19 by(auto) |
19 by(auto) |
20 (*>*) |
20 (*>*) |