src/Doc/Tutorial/Misc/Tree2.thy
changeset 67406 23307fd33906
parent 58860 fee7cfa69c50
child 67613 ce654b0e6d69
equal deleted inserted replaced
67405:e9ab4ad7bd15 67406:23307fd33906
     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 (*>*)