\begin{slide}{Rekursions-Schemata (1)}

\begin{verbatim}
inorder :: Tree a -> [a]
inorder t = case t of
    Leaf {} -> []
    Branch {} -> inorder (left t) 
        ++ [key t] ++ inorder (right t)
sum :: Tree Int -> Int
sum t = case t of
    Leaf {} -> 0
    Branch {} -> sum (left t) 
        + key t + sum (right t)
\end{verbatim}
Codeverdopplung $\to$ Refaktoring!

\end{slide}

\begin{slide}{Rekursions-Schemata (2)}

das ist der Plan\dots
\begin{verbatim}
f :: Tree a  -> b
f t = case t of
    Leaf {} ->  g
    Branch {} -> 
        h (f (left t)) (key t) (f (right t))

f = inorder
g = [] ; h x y z = x ++ [y] ++ z
\end{verbatim}
 
\end{slide}

\begin{slide}{Rekursions-Schemata (3)}

\dots und den kann man tatsächlich hinschreiben!
\begin{verbatim}
fold :: ... -> ... -> Tree a  -> b
fold g h t = case t of
    Leaf {} ->  g
    Branch {} -> 
        h (fold g h $ left t)
          (key t) (fold g h $ right t))
\end{verbatim}
\begin{verbatim}
inorder = fold [] ( \ x y z -> x ++ [y] ++ z )
sum     = fold ... ...
\end{verbatim} 
Anzahl der Blätter? Verzweigungen? Tiefe?

\end{slide}

\begin{slide}{Rekursions-Schemata (4)}

\dots für Listen?

\begin{verbatim}
data [a] = a : [a] | []

foldr g z l = case l of
    x : xs -> ...
    []     -> ...

length  :: [a] -> Int ; length = foldr ... ...
reverse :: [a] -> [a]
map     :: (a -> b) -> [a] -> [b]
filter  :: (a -> Bool) -> [a] -> [a]
\end{verbatim}

\end{slide}

\begin{slide}{Rekursions-Schemata}

Datentyp $\to$ Schema: Konstruktor $\to$ Funktion

\bigskip

ein Rekursionsschema für ein Objekt
eines algebraischen Datentyps auswerten:

jeden Konstruktor ($=$ Funktionssymbol)
durch die entsprechende Funktion ersetzen

\bigskip

Datentyp $=$ Signatur $\Sigma$,\\
Rekursionsschema $=$ $\Sigma$-Algebra.

\end{slide}
