
\begin{slide}{Rekursion über Bäume (Beispiele)}
\begin{verbatim}
data Tree a    = Leaf 
  | Branch ( Tree a ) a ( Tree a )
summe :: Tree N -> N
summe t = case t of
  Leaf -> Z
  Branch l k r -> 
    plus (summe l) (plus k (summe r ))
preorder :: Tree a -> List a
preorder t = case t of
  Leaf -> Nil
  Branch l k r -> 
   Cons k (append (preorder l) 
                  (preorder r))
\end{verbatim}
\end{slide}


\begin{slide}{Rekursion über Bäume (Schema)}

gemeinsame Form dieser Funktionen:
\begin{verbatim}
f :: Tree a -> b
f t = case t of
  Leaf         -> ...
  Branch l k r -> ... (f l) k (f r)
\end{verbatim}
dieses Schema ist eine Funktion höherer Ordnung:
\begin{verbatim}
fold :: ( ... ) -> ( ... ) -> ( Tree a -> b )
fold leaf branch = \ t -> case t of
  Leaf -> leaf
  Branch l k r -> 
     branch (fold leaf branch l) k 
            (fold leaf branch r)
summe = fold Z ( \ l k r -> plus l (plus k r ) )
\end{verbatim}


  
\end{slide}
