src/Doc/Tutorial/Misc/Tree2.thy
changeset 69597 ff784d5a5bfb
parent 69505 cc2d676d5395
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
     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 (*>*)