equal
deleted
inserted
replaced
1 (*<*) |
1 (*<*) |
2 theory Tree2 imports Tree begin |
2 theory Tree2 imports Tree begin |
3 (*>*) |
3 (*>*) |
4 |
4 |
5 text\<open>\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>\<open>flatten\<close> from trees to lists. The straightforward version of |
7 @{term"flatten"} is based on \<open>@\<close> and is thus, like @{term"rev"}, |
7 \<^term>\<open>flatten\<close> is based on \<open>@\<close> and is thus, like \<^term>\<open>rev\<close>, |
8 quadratic. A linear time version of @{term"flatten"} again reqires an extra |
8 quadratic. A linear time version of \<^term>\<open>flatten\<close> again reqires an extra |
9 argument, the accumulator. Define\<close> |
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 (*>*) |