\begin{slide}{Strukturerhaltende Folds}

elementweise Operation:

Argument und Resultat haben gleiche Struktur,
aber (mglw.) verschiedene Elemente:
\begin{verbatim}
map :: (a -> b) -> (Tree a -> Tree b)
map f = fold Leaf 
   ( \ l k r -> Branch l (f k) r )

map :: (a -> b) -> ([a] -> [b])
map f = foldr ( \ x ys -> f x : ys ) []

map length [ "foo", "bar" ] = [ 3, 3 ]
\end{verbatim}

Ü: Unterschiede zw. \verb|map reverse| 
und \verb|reverse|
  
\end{slide}

\begin{slide}{Programmtransformationen}

Komposition von Funktionen:
\begin{verbatim}
(f . g) = \ x -> f (g x)
\end{verbatim}
Ü: Typ von \verb|(.)|. Bem: Notation leider falschherum.

Satz: 
(wenn \verb|map| \glqq richtig\grqq\ definiert ist, gilt:)
\begin{itemize}
\item \verb|map id == id|
\item  \verb|map (f . g) == map f . map g|
\end{itemize}

Anwendung: Einsparung von Zwischen-Strukturen.

\end{slide}

\begin{slide}{Programmtransformationen (II)}

Satz: 
(wenn \verb|map| \glqq richtig\grqq\ definiert ist, gilt:)
\begin{itemize}
\item 
\verb|foldr nil cons . map f == foldr .. ..| 
\item
desgl. für Bäume
\end{itemize}


\end{slide}
