src/Doc/Tutorial/Misc/Tree2.thy
author wenzelm
Sun, 20 May 2018 22:04:17 +0200
changeset 68237 e7c85e2dc198
parent 67613 ce654b0e6d69
child 69505 cc2d676d5395
permissions -rw-r--r--
removed junk;

(*<*)
theory Tree2 imports Tree begin
(*>*)

text\<open>\noindent In Exercise~\ref{ex:Tree} we defined a function
@{term"flatten"} from trees to lists. The straightforward version of
@{term"flatten"} is based on @{text"@"} and is thus, like @{term"rev"},
quadratic. A linear time version of @{term"flatten"} again reqires an extra
argument, the accumulator. Define\<close>
(*<*)primrec(*>*)flatten2 :: "'a tree \<Rightarrow> 'a list \<Rightarrow> 'a list"(*<*)where
"flatten2 Tip xs = xs" |
"flatten2 (Node l x r) xs = flatten2 l (x#(flatten2 r xs))"
(*>*)

text\<open>\noindent and prove\<close>
(*<*)
lemma [simp]: "\<forall>xs. flatten2 t xs = flatten t @ xs"
apply(induct_tac t)
by(auto)
(*>*)
lemma "flatten2 t [] = flatten t"
(*<*)
by(simp)

end
(*>*)