%\documentclass{beamer}

\mode<presentation>
{
  \usetheme[compress]{Singapore}
  % possiblities Singapore, Malmoe, Dresden 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% /usr/share/texmf/tex/latex/beamer/base/themes/outer/beamerouterthememiniframes.sty
% geaendert
% navigation rauskommentiert!!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  \setbeamercovered{transparent}
}

% removes the navigation symbols 
\setbeamertemplate{navigation symbols}{} 

%color setting more or less matching U of A colors
\setbeamercolor*{palette secondary}{use=structure,fg=white,bg=structure.fg!55!black}
\setbeamercolor*{palette tertiary}{use=structure,fg=white,bg=red!50!black}
\setbeamertemplate{caption}[numbered]

%\usepackage{beamerthemeshadow}
\usepackage{lmodern}

\usepackage{tikz}
%\usepackage{tikz-qtree}
\usepackage{tkz-graph}
\usetikzlibrary{arrows,shapes,positioning}
%\usetikzlibrary{shapes.multipart}
%\usepackage{arrows}
%\usepackage{tikz-pgf}
\usepackage{scalefnt}

\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{amsfonts}
%
\usepackage{longtable} 
%\usepackage{moreverb} 
\usepackage{fancyvrb}
\usepackage{color}
%
%\usepackage{mpmulti}
\usepackage{xmpmulti}
%

%% Aussehen/Style
%\usepackage{beamerthemeshadow}

%% for including video/audio
%\usepackage{multimedia} %needs hyperref-package

%% aktive Referenzen
\usepackage{hyperref}

%%****rote schluesselwoerter****
\newcommand{\keyword}[1]{
  {\color{red}\texttt{\textbf{#1}}}
}
%%***parbox definieren
\newcommand{\kasten}[1]{
\begin{center}
  \fbox{\parbox{10cm}{#1}}
\end{center}
}
%
\newcommand{\doppelKasten}[1]{
\begin{center}
  \fcolorbox{red}{white}{\fcolorbox{red}{white}{\parbox{0.9\textwidth}{#1}}}
\end{center}
}

\newcommand{\doppelKastenOhneCenter}[1]{
  \fcolorbox{red}{white}{\fcolorbox{red}{white}{\parbox{0.9\textwidth}{#1}}}
}

%Definieren uns farbigen Quellcode
%\usepackage{color}
\definecolor{dkgreen}{rgb}{0,0.6,0}
%definecolor{gray}{rgb}{0.5,0.5,0.5}
%definecolor{mauve}{rgb}{0.58,0,0.82}
 
%Damit wir Quellcode nutzen können.
\usepackage{listings}

\lstdefinestyle{highlight}{
  keywordstyle=\color{red},
  commentstyle=\color{green},
  stringstyle=\color{dkgreen}
}

\lstloadlanguages{{XSLT}}
\lstloadlanguages{xml}
\lstloadlanguages{java}
\lstloadlanguages{Caml}

%\lstset{numbers=left,
\lstdefinestyle{xslt}{
        language=XSLT,
        numbers=left,
	numberstyle=\tiny,
	numbersep=5pt,
	breaklines=true,
	showstringspaces=false,
	frame=l ,
	xleftmargin=15pt,
	xrightmargin=15pt,
	stepnumber=1,
        tagstyle=\color{black!80},
        basicstyle=\footnotesize{\color{black!80}},
        keywordstyle={\color{red}\bf{}},
        commentstyle=\color{green!80},
        stringstyle=\color{dkgreen!80},
        moredelim=**[is][\pause{\color{black}\lstset{style=highlight}}]{@}{@},
        morekeywords={xs:schema,xs:element,xs:complexType,xs:sequence,xs:attribute
        },
}

\lstdefinestyle{java}{
      %  font=\tiny,
        language=java,
        numbers=left,
	numberstyle=\tiny,
	numbersep=5pt,
	breaklines=true,
	showstringspaces=false,
	frame=l ,
	xleftmargin=15pt,
	xrightmargin=15pt,
	stepnumber=1,
        basicstyle=\scriptsize{\color{black!80}},
        keywordstyle={\color{red}\bf{}},
        commentstyle=\color{green!80},
        stringstyle=\color{dkgreen!80},
        moredelim=**[is][\pause{\color{black}\lstset{style=highlight}}]{@}{@},
}

\lstdefinestyle{ocaml}{%
  language=[Objective]Caml,
  numbers=left,
  numberstyle=\tiny,
  numbersep=5pt,
  breaklines=true,
  showstringspaces=false,
  frame=l ,
  xleftmargin=15pt,
  xrightmargin=15pt,
  stepnumber=1,
  basicstyle=\footnotesize{\color{black!80}},
  keywordstyle={\color{red}\bf{}},
  commentstyle=\color{green!80},
  stringstyle=\color{dkgreen!80},
  moredelim=**[is][\pause{\color{black}\lstset{style=highlight}}]{§}{§},
}

\lstdefinestyle{ocaml2}{%
  language=[Objective]Caml,
  numbers=left,
  numberstyle=\tiny,
  numbersep=5pt,
  breaklines=true,
  showstringspaces=false,
  frame=l ,
  xleftmargin=15pt,
  xrightmargin=15pt,
  stepnumber=1,
  basicstyle=\footnotesize{\color{black!80}},
  keywordstyle={\color{red}\bf{}},
  commentstyle=\color{green!80},
  stringstyle=\color{dkgreen!80},
  moredelim=**[is][\pause{\color{black}\lstset{style=highlight}}]{§}{§},
}

%%**********************
%% Titelblatt-Einstellungen

\title{Einführung in die Funktionale Programmierung}
\subtitle{Am Beispiel von OCaml} 

\author{Michael Dienert}

\institute{Walther-Rathenau-Gewerbeschule \\ Freiburg}
\date{\today}


% Delete this, if you do not want the table of contents to pop up at
% the beginning of each section:
\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Inhalt}
    {
    \tableofcontents[currentsection]
        }
  \end{frame}
}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 
%\beamerdefaultoverlayspecification{<+->}


\begin{document}

\maketitle

\tableofcontents

%
%-------------------------------------------------(<frame>)
%
\begin{frame}
  \titlepage
\end{frame}
%
%-------------------------------------------------(</frame>)
%
%
%#################################################################################
% 
\section{Welche funktionale Sprache wählen wir?}
\subsection<article>{Welche funktionale Sprache soll ich lernen?}
%
%
\begin{frame}%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Welche funktionale Sprache soll ich lernen?}}
  % 
    % 
    \pause Eine kleine Auswahl an funktionalen Sprachen:%
    % 
    \begin{description}
      \pause \item[Lisp]: Lisp ist die zweitälteste Hochsprache
      (1958), die heute noch verwendet wird und Bedeutung hat (nach
      FORTRAN)%
      % 
      \pause \item[Scheme]: Scheme ist ein Lisp-Dialekt und wird vor
      allem am MIT (\textit{Massachusetts Institute of Technology}) in
      der Lehre benutzt. \pause Das zugehörige Lehrbuch
      (\textit{Structure and Interpretation of Computer Programs}) ist
      frei verfügbar, somit eignet sich Scheme sehr gut um funktionales
      Programmieren zu erlernen.%
      %
      \pause \item[Haskell:] Haskell ist eine strikt funktionale
      Sprache, was sie für den Einsteiger weniger geeignet
      macht. \pause Z.B. sind IO-Operationen immer mit einer Zuweisung
      verbunden und damit rein funktional nicht darstellbar.%
      % 
    \end{description}
\end{frame}
%
%#################################################################################
%
\begin{frame}%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Welche funktionale Sprache soll ich lernen?}}
  % 
    % 
    \pause Weitere funktionale Sprachen:%
    % 
    \begin{description}
      \pause \item[OCaml:] OCaml hat neben funktionalen auch
      imperative Eigenschaften. OCaml wird vom französchischen
      \textit{Institut national de recherche en informatique et en
        automatique (INRIA)} entwickelt.%
      % 
      \pause \item[F\#:] F\# ist stark von OCaml beeinflusst. Man soll
      teilweise sogar OCaml-Code mit dem F\#-Compiler übersetzen
      können. \pause Da die Entwicklung von F\# aber von \textit{Mordor} aus
      gesteuert wird, scheidet es für uns aus und wir wählen OCaml.%
      % 
    \end{description}
    \pause {\small Zugegeben, die Bedeutung von OCaml geht nach einem Hype so
    um ca. 2005 herum zurück. Aber hier geht es um den Einstieg in die
    funktionale Programmierung, Scheme darf ich nicht nehmen, und dann
    beleibt immer noch die F\#-Option, für die, die ihre Seele
    verkaufen wollen.}
\end{frame}
%
%#################################################################################
%
\section{Einführung: wo liegt der Unterschied zur imperativen
  Programmierung}
\subsection<article>{Imperative Programmierung}
%
%
\begin{frame}%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Imperative Programmierung}}
  % 
  \begin{itemize}%
    % 
    \pause \item Imperative Programmierung orientiert sich an der
    \pause \textit{Funktionsweise der CPU} \pause $\Rightarrow$
    Speichermodell, Rechenwerk, Ein- / Ausgabe. \pause Beispiele: C,
    C++, Java, Pascal, Fortran, Algol, ...%
    % 
    \begin{description}
      % 
      \pause \item[Variablen] sind nichts anderes als {\color
        {red} gut lesbare Namen für \textit{Speicheradressen}}
      % 
      \pause \item[Kontrollstrukturen] bringen die
      \texttt{jmp}-Befehle des Prozessors in eine für Menschen lesbare
      Form.%
      % 
      \pause \item[Funktionen] oder \textit{Methoden} sind nichts
      anderes als \textit{Unterprogramme}, zu denen das Hauptprogramm
      mit \texttt{jmp}-Befehlen verzweigt.
      % 
    \end{description}
    % 
  \end{itemize}
\end{frame}
%
%#################################################################################
% 
\begin{frame}%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Imperative Programmierung}}
  % 
  \begin{itemize}
    % 
    \pause \item Algorithmen werden mit Kontrollstrukturen und
    Anweisungen \pause (z.B. i=i+1;) formuliert%
    % 
    \pause \item Die Anweisungen können globale und lokale Variablen
    und damit den \pause \textit{Maschinenzustand ändern}.
    % 
    \pause \item {\color{red}\textbf{Problem}:} \pause der Maschinenzustand
    hängt von der \pause \textit{Reihenfolge der Ausführung} und
    den \pause \textit{Ausgangswerten der Variablen} ab%
    % 
    \pause \item Bei komplexen Algorithmen ist es so gut wie unmöglich
    vorherzusagen, ob ein ungewollter Maschinenzustand auftreten kann.%
 \end{itemize}
\end{frame}
%
%#################################################################################
% 
\subsection<article>{Funktionale Programmierung}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionale Programmierung}}
  % 
  \begin{itemize}
    \pause \item Die funktionale Programmierung orientiert
    sich am \textit{mathematischen Funktionsbegriff}%
    % 
    \pause
    \begin{description}
    \item[Funktion:] eine Funktion ordnet jedem Element der
      Definitionsmenge \textbf{D} {\color{red}genau ein} Element der
      Ergebnismenge \textbf{Z} zu.
    \end{description}
    % 
    \pause \item Die Algorithmen einer funktionalen Programmiersprache
    basieren auf \textit{Ausdrücken}, die ausgewertet werden.%

    \pause \item Ein Ausdruck ist eine Kombination von
    \textit{Funktionen}, \textit{Operatoren} und \textit{Werten}, die
    einen \textit{Wert} zurückliefern, also \textit{ausgewertet}
    werden können.  Beispiele:
      \begin{itemize}
      \pause \item \verb#16 + 3 * 8#
      \pause \item \verb#sqrt 2.0#
      \pause \item \verb#2 < 3#
      \pause \item \verb#2.0 > 3.0#
      \pause \item \verb#2 + sum 3 4#
      \end{itemize}
    \end{itemize}
    % 
\end{frame}
%
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionale Programmierung}}
  % 
  \begin{itemize}
    \pause \item Die Variablen einer funktionalen Programmiersprache
    bezeichnen \textit{Werte} und keine Speicheradressen!\\%
    \pause ~~$\Rightarrow$~~
    % 
    \pause \textbf{Es gibt keine Zuweisung!!!}% 
    % 
    \pause \item Es erfolgt kein \textit{Ablauf von Anweisungen}, sondern eine
    \textit{Auswertung von Ausdrücken}.%
%
    \pause \item Die Auswertung ist eine mathematische \textit{Gleichungsumforumung}

 \end{itemize}
\end{frame}
%
%#################################################################################
% 
\subsubsection<article>{Einige OCaml-Operatoren}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionale Programmierung und
      einige OCaml operatoren}}
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§  let dreifach (x:float) = 3.0 *. x§
§§  let inc (x:float) = x +. 1.0§
§§  Anwendung:§
§§  inc(dreifach 7.0 -. inc 2.0)§
§§  Umformung:§
§§  inc(3.0 *. 7.0 -. 2.0 +. 1.0)§
§§  inc(21.0 -. 3.0)§
§§  inc(18.0)§
§§  (18.0 +. 1.0)§
§§  19§
\end{lstlisting}
\begin{itemize}
  \pause \item Kurzer erster OCaml-Syntax-Einschub: \pause es gibt
  keine überladenen Operatoren!%
  \pause \item es gibt Operatoren fuer Rechnen mit Integerwerten:\\
  \pause ~~+~~, ~~-~~, ~~*~~, ~~/~~ %
  \pause \item und entsprechend Operatoren fuer das Rechnen mit
  Fliesskommazahlen: \pause ~~+.~~ , ~~-.~~ , ~~*.~~, ~~/.~~ %
\end{itemize}
\end{frame} 
%
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionale Programmierung: Wiederholungen}}
%
  \begin{itemize}
    % 
    \pause \item Schleifen in imperativen Programmiersprachen arbeiten
    mit Zuweisungen%
    % 
    \pause \item Da es in der funktionalen Programmierung keine
    Zuweisungen gibt, gibt es auch keine Schleifen%
    % 
    \pause \item Wiederkehrende Operationen können in \textit{rein
    funktionalen} Sprachen nur mittels \textit{Rekursion} gelöst werden.
  \end{itemize}
%
\end{frame}
%
%#################################################################################
% 
\section{Recursion}
\subsection<article>{Rekursionsbeispiel}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Rekursionsbeispiel}}
%
  \pause
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§  let rec fakultaet (n:int) = §
§§  if n=0 || n=1 then 1 §
§§  else n * fakultaet (n-1);; §
§§ ------------------------------------ §
§§  Auswertung mit Gleichungsauflösung §
§§  fakultaet 3 §
§§  = 3 * ( fakultaet(2) ) §
§§  = 3 * ( 2 * ( fakultaet(1) ) ) §
§§  = 3 * ( 2 * (1) ) §
§§  = 3 * ( 2 * 1 ) §
§§  = 3 * ( 2 ) §
§§  = 3 * 2 §
§§  = 6 §
\end{lstlisting}
% 
\pause Nachteil: Speicherbedarf wächst linear mit der Anzahl an
Rekursionsschritten%
\end{frame}
%
%#################################################################################
% 
\subsection<article>{Endrekursion}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Endrekursionsbeispiel}}
  \pause Das Falkultätsbeispiel mit \textit{Endrekursion}.
  \pause Hier ist der Speicherbedarf unabhängig von der Anzahl der
  Rekursionen:%
\pause
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§  let facultaet n = §
§§    let rec facHelp n akku = §
§§       if n = 0 then akku §
§§       else facHelp (n-1) (n*akku) §
§§    in facHelp n 1;; §
§§ ---------------------------------- §
§§  facultaet 3 §
§§  = facHelp 3 1 §
§§  = facHelp (3-1) (3*1) §
§§  = facHelp  2     3    §
§§  = facHelp (2-1) (2*3) §
§§  = facHelp  1     6    §
§§  = facHelp (1-1) (1*6) §
§§  = facHelp  0     6    §
§§  = 6
\end{lstlisting}
\end{frame}
%
%#################################################################################
% 
\section{Wichtige Eigenschaften von OCaml}
\subsection<article>{Funktionsaufrufe, Typisierung}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Erklärungen zu den Beispielen}}
  \begin{itemize}
    \pause \item Funktionsaufrufe finden \textbf{ohne Klammern} und
    \textbf{ohne Kommas} statt! Klammern sind nur notwendig, damit der
    Compiler Ausdrücke in der richtigen Reihenfolge auswerten kann.%
    \pause ~~Beispiel: 
\begin{lstlisting}[style=ocaml, gobble=1]
§§ f 5 (g "hello") 3    (* f hat drei argumente, g hat ein argument *) §
§§ f (g 3 4)            (* f hat ein argument, g hat zwei argumente *) §
\end{lstlisting}

    \pause \item Typdeklarationen: \textit{bezeichner : typ}
    \pause \item OCaml ist \textit{streng} typisiert
    \pause \item OCaml arbeitet mit \textit{impliziter} Typisierung:

\begin{lstlisting}[style=ocaml, gobble=1]
 # let f a b = a +. b;;
 val f : float -> float -> float = <fun>
\end{lstlisting}

  \end{itemize}
\end{frame}
%
%#################################################################################
% 
\subsection<article>{let-Bindings}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Erklärungen zu den Beispielen: let-Bindings}}
  \begin{itemize}
    % 
    \pause \item Deklarationen müssen das Schlüsselwort \keyword{let}
    verwenden: %
\pause
\begin{lstlisting}[style=ocaml, gobble=1]
  let name = expression
\end{lstlisting}
    % 
    \pause \item mit \keyword{let} wird ein beliebiger
    \textit{Ausdruck} an einen Bezeichner \textbf{gebunden}. \pause
    ~~$\Rightarrow$~~ let-Binding%
    % 
    \pause \item Der Bezeichner wird somit zum \textit{Aliasnamen} für den
    gesamten Ausdruck. Überall wo im Folgenden der Bezeichner steht,
    kann man sich den gesamten Ausdruck eingesetzt denken.%
    % 
  \end{itemize}
\end{frame}
%
%#################################################################################
%  
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Erklärungen zu den Beispielen: let-Bindings, Fortsetzung}}
  \begin{itemize}
    % 
    \pause \item Bindungen \textit{innerhalb} eines Ausdrucks, also
    lokale Bindungen werden mit dem Schlüsselwort \keyword{in}
    deklariert:
\begin{lstlisting}[style=ocaml, gobble=1]
  let name = expression in ... ;;
\end{lstlisting}
% 
\pause Hier gilt die Bindung nur ab dem Schlüsselwort \keyword{in} bis zu
den doppelten Strichpunkten \keyword{;;}
% 
    \pause \item Eine Funktion kann erst aufgerufen werden, wenn sie
    zuvor komplett deklariert wurde. Das geht bei rekursiven Aufrufen
    natürlich nicht, weshalb hier mit \keyword{let rec} gearbeitet
    werden muss.%

% 
  \end{itemize}
\end{frame}
%
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Endrekursionsbeispiel ohne lokale
      Deklaration}} \pause Nochmals das Falkultätsbeispiel mit
  \textit{Endrekursion}, diesmal aber \textit{ohne} lokale
  Deklaration:%
  \pause
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§  (*diesmal wird die hilfsfunktion global deklariert *) §
§§  let rec facHelp n akku = §
§§    if n = 0 then akku §
§§    else facHelp (n-1) (n*akku);; §
§§  §
§§  let facultaet n = §
§§    facHelp n 1;; §
§§  §
§§  facultaet 5;; §
\end{lstlisting}
\end{frame}
%
%#################################################################################
% 
\subsection<article>{Generische Typisierung}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Generische Typisierung}}
  
  OCaml erlaubt auch Funktionen mit generischem Rückgabetyp.
  
  \pause Beispielcode:

\begin{lstlisting}[style=ocaml, gobble=1]
§§  let x_oder_y testfunktion x y = §
§§    if testfunktion x then x else y;; §
§§  val x_oder_a : ('a -> bool) -> 'a -> 'a -> 'a = <fun>  §
\end{lstlisting}

\pause Der Compiler kann hier noch nicht festlegen:

\begin{itemize}
  \pause \item Welchen Typ das Argument der \verb+testfunktion+ hat%
  \pause \item Welchen Typ die Argumente von \verb+x_oder_y+ haben%
  \pause \item Welchen Typ der Rückgabewert hat%
  \pause \item OCaml verwendet daher eine sog. \textit{type variable}:
  \pause \verb+'a+%
\end{itemize}
\end{frame}
% 
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Generische Typisierung}}
  
  \pause Zwei Testfunktionen:

\begin{lstlisting}[style=ocaml, gobble=1]
§§ let groesserDrei x = §
§§   x > 3;; §

§§ let laengerDrei s = §
§§   String.length s > 3;; §
\end{lstlisting}

\pause und das Ergebnis der Aufrufe:

\begin{lstlisting}[style=ocaml, gobble=1]
§§ x_oder_y groesserDrei 1 (-7);; §
§§ - : int = -7 §

§§ x_oder_y laengerDrei "foooooo" "bar";; §
§§ - : string = "foooooo" §
\end{lstlisting}

\end{frame}
% 
%#################################################################################
% 
\subsection<article>{Datenstrukturen}
\subsubsection<article>{Tupel, Records, Listen und Pattern Matching}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Tupel, Records, Listen und Pattern Matching}}
  \begin{itemize}
    \pause \item OCaml stellt grundsätzlich zwei Datenstrukturen bereit: \pause
    Tupel und \pause Listen%
    \pause \item Records sind eine Sonderform der Tupel. Dazu später
    mehr.%
    \pause \item Tupel sind Sammlungen von Werten
    \textit{verschiedenen} Typs.%
    \pause \item Die Anzahl der Elemente eines Tupels ist
    \textit{fest}.%
    \pause \item Listen sind Sammlungen von Elementen
    \textit{gleichen} Typs.%
    \pause \item Die Anzahl der Elemente einer Liste ist beliebig.%
    \pause \item Auf die Elemente eines Tupels oder einer Liste kann
    mit \textit{pattern matching} zugegriffen werden.%
    \pause \item Pattern Matching ist eine erweiterte Form der
    \textit{switch-case} Anweisung aus C und Java.%
    \pause \item alles Weitere folgt in Code-Beispielen
  \end{itemize}
\end{frame}
%
%#################################################################################
% 
\subsection<article>{Beispiele zu Tupel, Listen, Pattern-Matching}
\subsubsection<article>{Beispiele zu Tupeln}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Beispiele zu Tupeln}}

\begin{itemize}  
\pause \item Die einzelnen Werte eines Tupels werden duch Kommas getrennt:
\pause
\begin{lstlisting}[style=ocaml, gobble=0]
let a_tuple = (3,"three");;
\end{lstlisting}

\pause \item Mit Patter-Matching werden die Einzelwerte ermittelt:
\pause
\begin{lstlisting}[style=ocaml, gobble=0]
let (x,y) = a_tuple;;
\end{lstlisting}
\pause \item Das Pattern hat hier den Wert \verb+(x,y)+
\pause \item Welchen Wert und welchen Typ haben x und y?
\end{itemize}

\end{frame}
%
%#################################################################################
% 
\subsubsection<article>{Beispiele zu Pattern-Matching}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Beispiele zu Pattern-Matching}}

\begin{itemize}  
\pause \item Noch ein Beispiel mit Pattern-Matching:

\pause
\begin{lstlisting}[style=ocaml, gobble=1]
§§ let distance (x1,y1) (x2,y2) = §
§§ sqrt ((x1 -. x2) ** 2. +. (y1 -. y2) ** 2.);; §
§§ let p1 = (1.0,0.0);; §
§§ let p2 = (0.0,1.0);; §
§§ distance p1 p2;; §
\end{lstlisting}
\pause \item Welcher Wert wird angezeigt?

\end{itemize}

\end{frame}
%
%#################################################################################
% 
\subsubsection<article>{Beispiele zu Listen}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Beispiele zu Listen}}
\begin{itemize}  
  \pause \item Die einzelnen Werte einer Liste werden durch
  Strichpunkte (Semikolon) getrennt: \pause
\begin{lstlisting}[style=ocaml, gobble=1]
§§ let liste = [1;2;3];; §
§§ (*alternativ*) §
§§ let liste = 1::2::3::[];; §
\end{lstlisting}

\pause \item der Operator \verb+::+ hängt ein Element \textbf{vor} die
Liste:

\begin{lstlisting}[style=ocaml, gobble=1]
§§ let listeNeu = 0::liste;; §
\end{lstlisting}

\pause \item der Operator \verb+@+ verkettet zwei Listen:

\begin{lstlisting}[style=ocaml, gobble=1]
§§ let listeLang = [1;2;3] @ [4;5;6] §
§§ liste @ listeNeu §
\end{lstlisting}

\end{itemize}

\end{frame}
\setbeamercovered{transparent}
%
%#################################################################################
% 
\subsubsection<article>{Beispiele zu Pattern-Matching und Listen}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Pattern-Matching und Listen}}
\begin{itemize}  
  \pause \item Pattern-Matching mit dem Schlüsselwort \verb+match+ und
  der Zeichenkombination \verb+->+%
%
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§ let meineLieblingsSprache languages = §
§§    match languages with §
§§    | erstesElement :: derGanzeRest -> erstesElement §
§§    | [] -> "OCaml" (* A good default! *) §
§§ ;; §

§§ meineLieblingsSprache ["Alemannisch";"English";"Spanish";"French"];; §
§§ meineLieblingsSprache [];; §
\end{lstlisting}

\end{itemize}

\end{frame}
%
%#################################################################################
% 
\subsubsection<article>{Eine Übungsaufgabe zu Pattern-Matching, Listen
und rekursiven Funktionen}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Übungsaufgabe zu Pattern-Matching,
      Listen und rekursiven Funktionen}}
  \begin{itemize}
    \pause \item Schreibe eine \textit{rekursive} Funktion \verb+sum+,
    die alle Werte einer Integer-Liste aufsummiert%
    \pause \item Hinweis: Pattern-Matching mit \verb+match+ verwenden.%
    \pause \item Schreibe eine Funktion \textit{trimmDoppler}, die zwei benachbarte
    Elemente, die den gleichen Wert haben, auf ein einzelnes Element
    reduzieren.%
  \end{itemize}
\end{frame}
%
%#################################################################################
% 
\subsubsection<article>{Lösung}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Lösung}}
%
%
\begin{lstlisting}[style=ocaml, gobble=1]
§§  let rec sum liste = §
§§     match liste with §
§§     | head :: tail -> head + sum tail §
§§     | [] -> 0 §
§§  ;; §
\end{lstlisting}

\begin{lstlisting}[style=ocaml, gobble=1]
§§ let rec trimDoppler liste = §
§§  match liste with §
§§  |[] -> [] §
§§  |[head] -> [head] §
§§  |e1 :: e2 :: rest -> §
§§   if e1 = e2 then trimDoppler (e1::rest) §
§§   else e1 :: trimDoppler (e2::rest) §
§§ ;; §
\end{lstlisting}


\end{frame}
%
%#################################################################################
% 
\subsection<article>{Quicksort}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Quicksort}}
%
  \begin{itemize}
    \pause \item Quicksort arbeitet nach dem römischen Prinzip:
    \textit{Teile und herrsche!}%
    \pause \item Um eine Liste zu sortieren, wird diese in zwei Listen
    geteilt, die einzeln sortiert werden.%
    \pause \item Das Teilen erfolgt nach diesem Algorithmus:
    \begin{itemize}
      \pause \item Wähle ein beliebiges Element der Liste, z.B. das
      \textit{Erste} (head)%
      \pause \item Dieses Element nennen wir \textit{Pivot-Element} %
      \pause \item Verschiebe alle Elemente der Liste, die kleiner
      sind als \textit{Pivot} in die linke Teilliste%
      \pause \item Verschiebe alle Elemente der Liste, die grösser
      sind als \textit{Pivot} in die rechte Teilliste.%
    \end{itemize}
    \pause \item Bearbeite die Teillisten nach dem gleichen Prinzip (rekursiv)
  \end{itemize}
%
\end{frame}
%
%#################################################################################
% 
\subsection<article>{Quicksort: Zahleneispiel}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Quicksort: Zahlenbeispiel}}
\begin{lstlisting}[style=ocaml, gobble=1]
§§     [10;13;17;4;5;2;7;3;1;11] §
§§     [4;5;2;7;3;1]--[10]--[13;17;11] §
§§                          [11]--[13]--[17] §
§§                                  []--[17]--[] §
§§                      []--[11]--[] §

§§     [2;3;1]--[4]--[5;7]§
§§               []--[5]--[7]§
§§                 []--[7]--[]§

§§     [1]--[2]--[3] §
§§           []--[3]--[]§
§§ []--[1]--[]§

§§ [1;2;3;4;5;7;10;11;13;17] §

\end{lstlisting}

\end{frame}
%
%#################################################################################
% 
\section<article>{Funktionen im Detail}
\subsection<article>{Funktionsdeklaration mit \texttt{fun}}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionsdeklaration mit \texttt{fun}}}
\setbeamercovered{transparent}
\begin{itemize}
  % 
  \pause \item  Bisher haben wir Funktionen so deklariert:
  \pause 
  \begin{lstlisting}[style=ocaml, gobble=1]
    let inc a  = a + 1;;
  \end{lstlisting}
  % 
  \pause \item Das ist eine vereinfachte Syntax (syntactic sugar) für
  die ausführliche Deklaration:%
  \pause
  \begin{lstlisting}[style=ocaml, gobble=1]
    let inc = fun a -> a + 1 ;;
  \end{lstlisting}
  % 
  \pause \item Wir haben gelernt, dass mit \verb+let+ Aliasnamen für
  Ausdrücke gebildet werden.%
  % 
  \pause \item Das heisst umgekehrt, dass die Deklaration mit
  \verb+fun+ einen ganz \textit{normalen, gleichberechtigten Ausdruck}
  darstellt:%
  % 
  \pause
  \begin{lstlisting}[style=ocaml, gobble=1]
    fun a -> a + 1 ;;
  \end{lstlisting}
  % 
\end{itemize}

\end{frame}
%
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionsdeklaration mit \texttt{fun}}}
\setbeamercovered{transparent}
Das bedeutet:
\begin{itemize}
  % 
  \pause \item Funktionsausdrücke kann man mit \verb+let+ an einen
  Namen binden: klar, hatten wir schon.%
  % 
  \pause \item Funktionsausdrücke können als Parameter anderer
  Funktionen auftreten.%
  % 
  \pause \item Funktionsausdrücke können als Ergebnis einer Funktion
  zurückgegeben werden.%
  % 
  \pause \item Funktionsausdrücke können in Datenstrukturen wie
  z.B. Listen oder Tupel gespeichert werden.%
\end{itemize}
\end{frame}
%
%#################################################################################
% 
%
%#################################################################################
% 
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Funktionsdeklaration mit \texttt{fun}}}
\setbeamercovered{transparent}
Beispiel:
\begin{lstlisting}[style=ocaml, gobble=1]
§§  let funkliste = 
    [ (fun x->x+1); (fun x->x+2); (fun x->x+3) ] ;; §

§§  let rec iterate l = §
§§     match l with §
§§     |[] -> 0 §
§§     |h::t -> print_int (h 5); iterate t;; §
  
§§  iterate funkliste;; §
\end{lstlisting}
\end{frame}
%
%#################################################################################
%
\subsection<article>{Currying: Funktionen mit mehreren Argumenten}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Currying: Funktionen mit mehreren Argumenten}}
  \setbeamercovered{transparent}
  \begin{itemize}
    \pause \item Funktionen in imperativen Sprachen sind nichts
    anderes wie Subroutinen%
    \pause \item Deren Parameter müssen beim Funktionsaufruf alle
    gleichzeitig festliegen%
    \pause \item In der Mathematik und in funktionalen Sprachen gilt
    das nicht:
    \pause $$ f(x) = x \cdot y + z $$
    % 
    \pause gleichzeitiges Anwenden der Paramter:
    % 
    \pause $$ f(3,4,5) = 3 \cdot 4 + 5 = 17 $$
    % 
    \pause partielle Anwendung:
    % 
    \pause $$ f(3,y,z) = g(y,z) = 3 \cdot y + z  $$
    % 
    \pause partielle Anwendung auf die neue Funktion g:
    % 
    \pause $$ g(4,z) = h(z) = 3 \cdot 4 + z $$ 
    % 
  \end{itemize}
\end{frame}
%
%#################################################################################
%
\subsection<article>{Currying: Funktionen mit mehreren Argumenten}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Currying: Funktionen mit mehreren Argumenten}}
  \setbeamercovered{transparent}
  \begin{itemize}
    \pause \item Die Umwandlung einer Funktion mit mehreren Argumenten
    in eine Funktion mit nur einem Argument wird \textit{Currying}
    oder auch \textit{Schönfinkeln} genannnt.%
    \pause \item Namensgeber: Die Mathematiker Haskell Curry (US),
    Moses Isajewitsch Schönfinkel (RU)
  \end{itemize}
\end{frame}
%
%#################################################################################
%
\subsection<article>{Currying: Funktionen mit mehreren Argumenten}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Currying: Funktionen mit mehreren Argumenten}}
  \setbeamercovered{transparent}
Ein Beispiel in OCaml:
\begin{lstlisting}[style=ocaml, gobble=1]
§§ let avg a b = (a+b)/2;;  §

§§ let avg = (fun a -> (fun b -> (a+.b) /. 2.));;
\end{lstlisting}

\end{frame}
%
%#################################################################################
%
\subsection<article>{Ist Java 8 eine funktionale Sprache?}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Ist Java 8 eine funktionale Sprache?}}
  \setbeamercovered{transparent}
  Zwei Artikel (englisch):
  \begin{itemize}
    \pause \item http://java.dzone.com/articles/
                                whats-wrong-java-8-currying-vs
    \pause \item http://docs.oracle.com/javase/tutorial/java/
                                javaOO/lambdaexpressions.html
  \end{itemize}
\end{frame}
%
%#################################################################################
%
\subsection<article>{Ist Java 8 eine funktionale Sprache?}
\begin{frame}[fragile]%-------------------------------------------------(<frame>)
  \only<presentation>{\frametitle{Ist Java 8 eine funktionale Sprache?}}
  \setbeamercovered{transparent}


Lösung zum Oracle-Beispiel in Ocaml:
\begin{lstlisting}[style=ocaml, gobble=0]
let rec filter list f g =
  match list with
  |[] -> []
  |(mail, laenderCode, geburtsJahr)::t ->
    if ((f laenderCode) && (g geburtsJahr))
    then (mail, laenderCode, geburtsJahr) :: filter t f g
    else filter t f g
;;

filter persoList (fun x -> x="us") (fun x -> x>1950));;
filter persoList (fun x -> x="de") (fun x -> x=1910));;
\end{lstlisting}

\end{frame}

%
%
%#################################################################################
% 
\begin{frame}
  \only<presentation>{\frametitle{Danksagung}}
  % 
 \begin{center}
  \only<presentation>{ \Large Vielen Dank f"ur's Zuh"oren und Mitmachen!   }
 \end{center}
\end{frame}

\end{document}



