- Explicitely passed pred_subset_eq and pred_equals_eq as an argument to the
to_set and to_pred attributes, because it is no longer applied automatically
- Manually applied predicate1I in proof of accp_subset, because it is no longer
part of the claset
- Replaced psubset_def by less_le
(*<*)
theory Tree2 imports Tree begin
(*>*)
text{*\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: *}
consts flatten2 :: "'a tree \<Rightarrow> 'a list \<Rightarrow> 'a list"
(*<*)
primrec
"flatten2 Tip xs = xs"
"flatten2 (Node l x r) xs = flatten2 l (x#(flatten2 r xs))"
(*>*)
text{*\noindent Define @{term"flatten2"} and prove
*}
(*<*)
lemma [simp]: "!xs. flatten2 t xs = flatten t @ xs";
apply(induct_tac t);
by(auto);
(*>*)
lemma "flatten2 t [] = flatten t";
(*<*)
by(simp);
end
(*>*)