% -*- LaTeX -*-
%
% Programmieren III Skript, V0.1
%
% Werner Dietl,    9620153
%
% $RCSfile: prog3.tex,v $ - $Author: rbla $
% $Revision: 1.7 $ - $Date: 1998/04/18 22:25:49 $
%

\documentclass[notitlepage,openany,a4paper,austrian]{report}

\usepackage{a4}
\usepackage{isolatin1}
\usepackage{babel}
\usepackage{fancyhdr}
\usepackage{alltt}
\usepackage{latexsym}
\usepackage{tabularx}
\usepackage{html}

% Papiergröße setzen
\setlength\textwidth{\paperwidth}
\setlength\textheight{\paperheight}
\if@twocolumn
  \addtolength\textwidth{-30mm}
  \addtolength\textheight{-40mm}
  \setlength\topmargin{-17.4mm}
\else
  \addtolength\textwidth{-40mm}
  \addtolength\textheight{-50mm}
  \setlength\topmargin{-12.4mm}
\fi
\setlength\oddsidemargin{.6\paperwidth}
\addtolength\oddsidemargin{-.6\textwidth}
\addtolength\oddsidemargin{-25.4mm}
\setlength\evensidemargin{.6\paperwidth}
\addtolength\evensidemargin{-.6\textwidth}
\addtolength\evensidemargin{-25.4mm}

% Kopf- und Fußzeilen
\pagestyle{fancy}
\lhead{Programmieren III}
\chead{\today}
\rhead{Vorlesung}
\lfoot{Werner Pohlmann}
\cfoot{Universität Salzburg}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}


% Umgebung für die Totenköpfe
\newenvironment{wichtig}{\vspace{3mm plus1mm minus 1mm} \bfseries }
                        {\marginpar{\LARGE !} \vspace{3mm plus1mm minus2mm} }

% Umgebung für Haskell-Code und Hugs-Befehle
\newenvironment{code}{\vspace{1mm plus1mm}\begin{alltt}}
                     {\vspace{1mm plus1mm}\end{alltt}}

% Kleine Randnotizen
\newenvironment{notiz}{\vspace{2mm plus1mm minus1mm}\footnotesize}
                      {\vspace{2mm plus1mm minus1mm}}

% Der Backslash
\begin{htmlonly}
  \newcommand{\bkslash}{\char92}
\end{htmlonly}

%begin{latexonly}
  \newcommand{\bkslash}{\symbol{'134}}
%end{latexonly}

\begin{document}

\begin{titlepage}
\null\vfil

\begin{center}
\Huge{
Programmieren III\\
Funktionale Programmierung\\
}
\vskip 3em

\LARGE{Dr. Werner Pohlmann}

\vskip 1.5em

\large{Wintersemester 97/98}
\end{center}

\vskip 10em

\huge{Vorwort}
\vskip 0.75em

\normalsize
Dieses Skriptum ist während der Vorlesung "`Programmieren III,
1. Teil"' zum Thema funktionale Programmierung entstanden. Der
Inhalt wurde direkt von den Folien des Dozenten Dr. Werner Pohlmann
übernommen, wobei kleinere Korrekturen während der Vorlesung berücksichtigt
wurden. Getippt wurde dieser Text von den beiden Tutoren Werner
Dietl und Ronald Blaschke im Satzprogramm \LaTeX.

Copyright liegt natürlich beim Dozenten bzw. bei der Universität Salzburg.
\vfil

\large{RCS Information}
\vskip 0.75em

\normalsize
\begin{code}
$Revision: 1.7 $ 
$Date: 1998/04/18 22:25:49 $
\end{code}

\null

\end{titlepage}


\tableofcontents


\chapter{Einführung}

\section{Zweck der Vorlesung}

\begin{itemize}
\item Grundkenntnisse / -fähigkeiten
\item am Beispiel einer modernen funktionalen Sprache
\item Verständnis für \emph{Zweck, Bedeutung, Probleme}
\end{itemize}


\section{Einschränkungen / Randbedingungen}

\begin{itemize}
\item \emph{sehr} enger zeitlicher Rahmen
\item Kenntnisse in imperativer Programmierung, Algorithmen und
      Datenstrukturen sind vorausgesetzt!
\end{itemize}


\section{Plan der Vorlesung}

\begin{tabular}{l@{ = }l}
Kapitel 1   & Einführung \\
Kapitel 2   & Rundreise durch Haskell \\
Kapitel 2+n & Vertiefung
\end{tabular}


\section{Überblick "`Höhere Programmiersprachen"'}

Man unterscheidet:

\begin{itemize}
\item imperative Programmiersprachen

z.\,B.: Fortran (1958, Backus), Algol 60, Algol 68, Cobol, PL1, Pascal,
Modula, \dots

\begin{tabularx}{\linewidth}{lX}
Wesentlich: &

\emph{Anweisungen} ( $\rightarrow$ "`imperativ"' ) mit
festgelegter \emph{Ausführungsreihenfolge} (Kontrollstrukturen) ändern
\emph{Programmvariable}.
\end{tabularx}

\begin{notiz} 
(\emph{Objektorientierte} Sprachen sind eine Form imperativer Sprachen; 
spezielle Definitionstechnik für Datenstrukturen ermöglicht 
evolutionäre / wiederverwendende Programmierung.)
\end{notiz}

Vorbild imperativer Sprachen:

\begin{tabularx}{\linewidth}{rX}
von-Neumann-Rechner = & aktive Zentraleinheit führt \emph{Befehle} aus,
die Werte in passivem \emph{Speicher} aktualisieren (lesen / schreiben)
\end{tabularx}

Wegen der Nähe zur klassischen Rechnerstruktur sind imperative Sprachen sehr
effizient zu implementieren!


\item funktionale Programmiersprachen

z.\,B.: Lisp (1960, McCarthy), Scheme, ML, FP, Hope, Miranda, \dots

\begin{samepage}
Charakteristisch:
\begin{itemize}
\item \emph{keine} Anweisungen
\item \emph{keine} Variablen
\item sondern: Programmierer definiert \emph{Funktion} (abgestüzt auf
andere Funktionen, Konstantenvereinbarungen, \dots) und spezifiziert
Ziele der Berechnung durch damit gebildeten \emph{Ausdruck}
\end{itemize}
\end{samepage}

\begin{notiz}
Manche "`funktionale Sprachen"' sind \emph{nicht rein} funktional!
\end{notiz}

\begin{tabularx}{\linewidth}{lX}
Vorbild: & Mathematik, speziell $\lambda$-Kalkül; Auswertung von Ausdrücken
durch \emph{Reduktion}, d.~h. schrittweise Transformation in die
einfachste Form (=~Wert).
\end{tabularx}

Keine direkte Entsprechung zur üblichen Rechnerstruktur;

Grundsätzlich schwieriger zu implementieren / weniger effizient;

Heute allerdings sehr gute (kompilierende) Implementierungen mit (bei
vernünftigen funktionalen Programmen) der imperativen Welt vergleichbaren 
Leistungen.


\item logische Programmiersprachen

insbesondere Prolog (1971, Colmerauer)

\begin{tabularx}{\linewidth}{lX}
Charakteristisch: &
gewünschtes Ergebnis wird mit Mitteln der Logik (also relational) definiert und
durch ein Beweisverfahren mit Hilfe einer Wissensbasis abgeleitet.
\end{tabularx}


$\Longrightarrow$ Teil 2 von Programmieren III

$\Longrightarrow$ funktionale Sprachen heißen auch \emph{applikativ},
logische Sprachen auch \emph{deklarativ}; (wobei letzterer Term auch für
funktionale Sprachen benutzt wird!)

\end{itemize}


\section{Funktionale Sprachen -- Was, Wie, Warum?}

\begin{itemize}
\item \textbf{Ursprung:} Lisp = Überlegungen aus der Theorie der 
Berechenbarkeit praktisch machen; 

\begin{itemize}
\item \emph{Anwendungen} zunächst beschränkt auf künstliche Intelligenz und 
Hochschulen;

\item seit den 70er Jahren neues und wachsendes Interesse an funktionaler
Programmierung;

\item Entwicklung von Sprachen, die durch angebotene Mittel und 
Implementierung auf \emph{Softwaretechniker} allgemein zielen.
\end{itemize}


\item \textbf{Gründe}: 
\begin{enumerate}
\item Kritik an imperativen Sprachen:

\emph{Semantik} (Wirkung, Verständnis vom Programm) durch
\emph{sich in der Zeit ändernden Zustand} (Stand der Bearbeitung, 
Variablenbelegung) gegeben -- und das ist zu schwer für das
menschliche Hirn!

\begin{samepage}
Beispiel: Partitionierung in Quicksort:

\begin{code}
i:=links; j:=rechts-1;

loop
  while a(i)<trenn loop i:=i+1; end loop;
  while a(j)>trenn loop j:=j-1; end loop;

  if i>=j then exit; end if;

  temp:=a(i); a(i):=a(j); a(j):=temp;

  i:=i+1; j:=j-1;
end loop;
\end{code}

?? Was gilt hier ??\\
?? Kommt man überhaupt dahin ??
\end{samepage}


imperative Programmierung ist mühsam, logisch anspruchsvoll und 
fehleranfällig, denn:
\begin{itemize}
\item Verhältnis von Zuweisung ``:='' und mathematischer Gleichheit ``='' 
ist (nicht nur für Anfänger) problematisch,

\item zwar reichliche Verwendung von Ausdrücken in den Anweisungen, aber
wegen mangelnder referentieller Transparenz (Kontextabhängigkeit) großer
Unterschied zu üblicher (mathematischer) Interpretation, z.\,B.:

\begin{code}
i: integer := 1;
a: array(1..10) of integer := (others=>0);

function f return integer is          -- Seiteneffekt
   begin i:=i+1; return i; end f;
\end{code}

dann z.\,B.:

\begin{code}
i:=i+f;
a(i):=f;
a(f):=a(f);
a(i+f):=i+f;
if 2*(i+f)=(i+f)+(i+f) then ...
...
\end{code}

Klar: Ziel nicht, Reihenfolge der Auswertung in Gebilden wie ``a(f):=a(f)''
zu normieren, sondern das Problem zu vermeiden!

\end{itemize}

\item positive Beiträge funktionaler Programmierung: andere
Formen von \emph{Abstraktion \& Modularisierung}

\begin{itemize}
\item Funktionen als "`Bürger erster Klasse"', also z.\,B.:
  \begin{itemize}
  \item Vektor von Funktionen,
  \item Funktion als Ergebnis und Parameter anderer Funktionen

        $\Rightarrow$ "`higher order functions"'
  \end{itemize}

vgl. "`map"',  "`fold"' in Programmieren II

vgl. Mathematik:

Differentiation als Transformation von reellen Funktionen, also:

\begin{code}
diff :: (Float->Float) -> (Float->Float)
diff(sin) = cos
\end{code}

ist in funktionaler Programmierung \emph{numerisch} ohne weiteres machbar!

\item verzögerte Auswertung ("`lazy evaluation"')
= rechne nur soviel, wie für das gewünschte Ergebnis nötig.

$\Rightarrow$ effiziente Kombination vom Programmteilen, die 
\emph{ohne} Rücksicht auf spezifische (beschränkte) Anwendung entworfen sind.


\begin{tabular}{ll}
Beispiel: & Test ob Zahl n prim ist \\

Annahme:  & es gebe Funktion \\
          & \texttt{divisors :: Int -> [Int]} \\
          & die \emph{Liste aller Teiler} einer gegebenen Zahl liefert \\

dann:     & \texttt{is\_prim n = divisors n == [1,n]}\\

wobei:    & falls n keine Primzahl ist wird \texttt{divisiors} nur \\
          & \emph{solange ausgewertet}, \emph{bis} erstes Gegenbeispiel \\
          & gefunden wurde.\\
also:     & Abbruchbedingung für \texttt{divisors} \emph{implizit},\\
          &  also \texttt{divisors} für ganz verschiedene Zwecke \\
          &  nutzbar (vgl.: wie macht man das in imperativer 
             Programmierung ?? )
\end{tabular}

\begin{wichtig}
Ferner: lazy evaluation erlaubt Arbeit mit (potentiell) unendlichen
Datenstrukturen (Listen, Bäumen, \dots).
\end{wichtig}

\end{itemize}

\end{enumerate}

\end{itemize}
          

\section{Haskell}

\begin{notiz}
(Name kommt vom Mathematiker Haskell Curry)
\end{notiz}

\begin{itemize}
\item ist moderne, anspruchsvolle, umfangreiche funktionale Sprache,

\item seit Anfang der 90'er von einer Gruppe von führenden
Wissenschaftlern (UK, USA, Dk) entwickelt und weiterentwickelt,
jetzt Version 1.4,

\item mehrere frei zugängliche Implementierungen (Compiler für Unix, 
Interpreter auch für andere Systeme), die an Universitäten (Chalmers,
Glasgow, Yale) entwickelt wurden und  "`industrial strength"' 
aufweisen,

\item 2 für Ausbildungszwecke, aber auch für Entwicklungsarbeiten,
angenehme interpretierende Umgebungen (Unix + PCs):
\begin{itemize}
\item Gofer (Spezialvariante)
\item Hugs (große Teilmenge von Haskell)
\end{itemize}

\end{itemize}

\section{Literatur}

\begin{itemize}
\item R.~Bird, P.~Waller:\\
 "`Introduction to Functional Programming"',\\
Prentice Hall, 1988\\
(klassisches Lehrbuch von zwei Spitzenleuten, benutzt nicht Haskell,
aber ähnliche Notation)

\item S.~Thompson:\\
"`Haskell, the craft of Functional Programming"',\\
Addison Wesley, 1996\\
(umfassendes, an Anfängern orientiertes Lehrbuch)

\item A.~J.~T.~Davies:\\
"`Functional Programming using Haskell"',\\
Cambridge University Press 1992\\
(als Einführung zu knapp, aber weiterführende Themen)

\item J.~Hughes:\\
"`Why Functional Programming Matters"',\\
The Computer Journal 32/2, 1989\\
(Zeitschriftenartikel, der Ziele der funktionalen Programmierung illustriert)
\end{itemize}

Letzteres ist im Haus elektronisch verfügbar; dito:
\begin{itemize}
\item Haskell-Report,
\item Hudak \& Fasel:  "`A Gentle Introduction to Haskell"'

(Obacht: viel lesbarer als Report, für Anfänger trotzdem nicht ganz
leicht \dots)
\end{itemize}

Viel Material im WWW verfügbar; gutes Archiv und Startadresse für
Weiteres ist Uni Aachen:

\texttt{http://www-i2.informatik.rwth-aachen.de/Forschung/FP/Haskell/}




\chapter{Kurze Rundreise durch Haskell}
% Zweck:  FIXME -- kann das denn keiner Lesen?

\section{Sitzungen mit Hugs}

Hugs ist ein Interpreter mit dem typischen  "`read-evaluate-write"'-Zyklus;

Hugs wertet aus:
\begin{itemize}
\item Haskell Ausdrücke

abgestützt auf Funktionssammlung im Standard-Prelude und/oder vom Benutzer
geladenen Dateien mit Haskell Definitionen.

\begin{wichtig}
Ausdrücke werden durch  "`Return"' abgeschlossen!
\end{wichtig}

\item durch ``:'' eingeleitete Kommandos, z.\,B.:

\begin{code}
:?      -- listet Kommandos auf
:quit   -- beendet die Sitzung
\end{code}

\end{itemize}

Einige Beispiele:

\begin{code}
1 pohlmann@okapi:hugs
      ___    ___   ___    ___   __________   __________
     /  /   /  /  /  /   /  /  /  _______/  /  _______/       Hugs 1.4
    /  /___/  /  /  /   /  /  /  / _____   /  /______
   /  ____   /  /  /   /  /  /  / /_   /  /______   /  The Nottingham and Yale
  /  /   /  /  /  /___/  /  /  /___/  /  _______/  /    Haskell User's System
 /__/   /__/  /_________/  /_________/  /_________/         Version 970410

   Copyright (c) The University of Nottingham and Yale University, 1994-1997.
    Bug reports: hugs-bugs@haskell.org.   Web: http://www.haskell.org/hugs.

Reading file "/usr/local/lib/hugs/lib/Prelude.hs":

Hugs session for:
/usr/local/lib/hugs/lib/Prelude.hs
Type :? for help
Prelude> 37-(2+5)
30
Prelude> 27-2+5
30
Prelude> min 3 4
3
Prelude> 3==4
False
Prelude> sum [1..10]
55
Prelude> reverse "Salzburg"
"grubzlaS"
Prelude>
\end{code}

Natürlich gibt's auch Fehlermeldungen --- für syntaktisch falsche Ausdrücke,
undefinierte Bezeichner oder unanständige Wünsche, \dots

\begin{enumerate}

\item \begin{alltt}
Prelude> 37-(2+5

ERROR: Syntax error in expression (unexpected end of input)
\end{alltt}

\item \begin{alltt}
Prelude> 37-(2+n)
ERROR: Undefined variable ``n''
\end{alltt}

\item \begin{alltt}
Prelude> let n=5 in 37-(2+n)  --so geht's, und dies ist ein Kommentar!
30
\end{alltt}

\item \begin{alltt}
Prelude> 37-True
ERROR: Bool is not an instance of class ``Num''
\end{alltt}

\item \begin{alltt}
Prelude> 37`div`(5-5)

Program error: {primDivInt 37 0}
\end{alltt}

\item \begin{alltt}
Prelude> let x=x in x
ERROR: Cannot find ``show'' function for:
*** expression : let {...} in x
*** of type    : a
\end{alltt}

\item \begin{alltt}
Prelude> let x::Int; x=x in x
{Interrupted!}                         -- mit Control-C
\end{alltt}

\end{enumerate}

Richtige Programmierer wollen natürlich ihre eigenen Funktionen, Konstanten, 
Datentypen, \dots definieren.
Solche  "`Script"' genannte Sammlungen von Definitionen werden in eine
Datei geschrieben und vor Gebrauch geladen:

\begin{code}
:load bla.bla
\end{code}

es ist sinnvoll, das Suffix  ``.hs'' zu verwenden (es gibt Werkzeuge, die
das brauchen);\\
außer solchen unstrukturierten Sammlungen gibt es auch einen
\emph{Modulbegriff} mit entsprechenden Bezügen (Export / Import), mehr
dazu später!

\begin{description}
\item[Beispiel:]

Datei \texttt{bla.bla}:

\begin{code}
area r=pi*r*r
  where pi=3.1416
\end{code}

Datei \texttt{error.bla}:

\begin{code}
area r=pi*r*r
  were pi=3.1416
\end{code}

Damit folgende Hugs-Sitzung:

\begin{code}
Prelude> :load bla.bla
Reading file "bla.bla":

Hugs session for:
/usr/local/lib/hugs/lib/Prelude.hs
bla.bla
Main> area 10
314.16
Main> :load error.bla
Reading file "error.bla":
Parsing
ERROR "error.bla" (line 2): Syntax error in input (unexpected `=')
\end{code}

\end{description}

Fehlermeldungen sind manchmal etwas schwierig zu interpretieren, woran oft
die ungewohnte Typ-Philosophie von Haskell schuld ist (siehe später).

Im ersten Beispiel gilt:

\begin{enumerate}
\item fehlende Klammer

\item n ist keine  "`Programmvariable"', sondern eine Variable im üblichen
\emph{mathematischen} Sinn, d.~h. ein \emph{Konstantenbezeichner}, wobei
der Wert natürlich willkürlich ist, aber festgelegt werden muß,

\item diese Festlegung kann man mit ``let'' machen,

\item Typfehler: die Subtraktionsoperation ist (überladen!) für mehrere
numerische Typen definiert, aber \texttt{Bool} ist kein numerischer Typ

\item Division durch 0 (\texttt{`div`} ist abgestützt auf eine speziellere
elementare Divisionsoperation)

\item \texttt{let x=x in x} führt auf Endlos-Schleife (=Wert von x ist 
undefiniert, wird aber  "`gesucht"';

hier: Typ von x unklar, deshalb kann nicht die geeignete Funktion ``show''
zur Ausgabe des Ergebnisses bestimmt werden,

\item hier wird das Ergebnis als ``Int'' deklariert, und schon sind wir in der
Endlos-Schleife \dots

\end{enumerate}

beachte:

\begin{itemize}
\item eine Gleichung wie \texttt{pi = 3.14} oder \texttt{area r = ...}
bindet einen \emph{Bezeichner} an einen \emph{Wert} (insbesondere ist also
pi Konstant, nicht Variable)

\item der Gebrauch einer ``where''-Klausel macht \texttt{pi} \emph{lokal} zur
Definition von \texttt{area} ($\Rightarrow$ später);

grundsätzlich ist ein Skript eine \emph{Menge} von Definitionen, die sich 
aufeinander beziehen können, aber z.\,B. auch:

\begin{code}
pi = 3.14      -- besser umbenennen: name clash mit Prelude!
area r = pi * r * r
circumference r = 2 * pi * r
\end{code}

\item beim Laden werden die Definitionen \emph{analysiert} und 
\emph{übersetzt}, aber werden auch bei dieser Gelegenheit
\emph{Syntaxfehler} im Skript gemeldet!

\end{itemize}

\section{Grundlegende Sprachelemente}
\subsection{Bezeichner}

Bezeichner für Funktionen (und Konstante = 0-stellige Funktionen) 
beginnen mit Kleinbuchstaben, gefolgt von Buchstaben, Ziffern, 
``\_'', ``\'{}''.

\begin{itemize}
\item Operatoren = 2-stellige Funktionen mit Infix-Gebrauch werden durch
Sonderzeichen gekennzeichnet

$\Rightarrow$ später,

\item es gibt einige reservierte Wörter und Sonderzeichenkombinationen,

$\Rightarrow$ Report

\item Bezeichner mit Großbuchstaben am Anfang werden für Typen (und zur 
Konstruktion derselben) verwendet, z.\,B. Int, Float, Bool
\end{itemize}

\begin{wichtig}
Der Prelude enthält viele in Haskell definierte \emph{Standardfunktionen}
(und Operatoren), die sich wiederum auf gewisse \emph{primitive} 
Funktionen abstützen

$\Rightarrow$ Report
\end{wichtig}


\subsection{Kommentare}
= ``\texttt{--}'' und Zeilenrest;

alternativ geht auch Einklammern mit ``\texttt{\{-}'' und ``\texttt{-\}}''.


\subsection{Klammerung / Klammerersparnis}

ist weitgehend an mathematischer Praxis orientiert, mit einer wichtigen
Ausnahme:

\emph{Funktionsapplikation} ist so häufig und fundamental, daß sie
\emph{höchste} Präzedenz bekommt (aber keine Klammerung nötig)

$\Rightarrow$ bequem aber tückisch (für Anfänger) % FIXME

\begin{wichtig}
\texttt{area 10 + 10} wird interpretiert als

\texttt{(area 10) + 10} $\Rightarrow$ 324.16

Will man \texttt{area(10+10)}, muß man das auch so schreiben !!

Mehr zum Thema später!
\end{wichtig}


\subsection{Layout}
Man kann in Haskell das Semikolon als \emph{Trennzeichen} (und 
geschwungene Klammern zur Gruppierung ähnlich ``begin - end'') nehmen,\\
aber es gibt eine bequemere \emph{Layout-Konvention} die
\emph{Abseits-Regel} (offside-rule):

\begin{itemize}
\item ist eine Zeile \emph{genauso weit} eingerückt wie die vorherige,
so bringt sie eine \emph{neue} Definition,

\item ist eine Zeile \emph{weiter} eingerückt, so enthält sie eine Fortsetzung
der vorher begonnenen Definition,

\item ist eine Zeile \emph{weniger} weit eingerückt, so beginnt eine neue
Gruppe von Definitionen
\end{itemize}

\begin{description}

\item[Beispiel:] Das Programm

\begin{code}
pi = 3.1416
   area r = pi * r * r
\end{code}

gibt einen Syntaxfehler!!

Richtig sind:

\begin{code}
pi = 3.1416;
   area r = pi * r * r
\end{code}

oder:

\begin{code}
pi = 3.1416
area r = pi * r * r
\end{code}

\end{description}


\begin{wichtig}
Achtung:
\begin{itemize}
\item Programmdateien besser nicht mit Proportionalschrift-Editor schreiben,

\item Verstöße gegen offside-rule ergibt manchmal (für den Anfänger) 
schwer verständliche Fehlermeldungen
\end{itemize}
\end{wichtig}


\subsection{Lokale Definitionen}

Mit \texttt{where}-Klauseln kann man \emph{Definitionen} qualifizieren,
d.\,h. auf eine untergeordnete Definition stützen:

\begin{code}
area r = pi * r * r
  where pi = 3.14 
\end{code}

Mit \texttt{let} kann man was Entsprechendes für \emph{Ausdrücke} tun:

\begin{code}
let x = 1 in x + 1

let x = 3
    f y = x + y
in f x 
\end{code}

\noindent
Damit dann Frage nach \emph{Gültigkeitsbereich / scope:}

\begin{enumerate}

\item Gültigkeit einer gewöhnlichen Definition ist das \emph{ganze Skript}, 
in dem sie enthalten ist;

Reihenfolge der Aufschreibung ist egal!

\item untergeordnete Definitionen gelten nur lokal, d.\,h. scope ist durch
die übergeordnete Definition gegeben:

% FIX-ME: Schachtelungs-Linien
\begin{code}
two_areas x y = area x + area y
   where area x = pi * square x 
      where pi = 3.14
            square x = x * x
\end{code}

beachte:

\begin{itemize}
\item zweite Schachtelung im Beispiel nicht nötig -- man kann alles "`flach"'
und in beliebiger Reihenfolge aufschreiben,

\item Wiederverwendung des Bezeichners x als Parameter \emph{verdeckt}
natürlich die frühere Einführung -- es gilt immer die "`lokalste"' 
Version % FIXME

\item Layout, \emph{Layout, \textbf{Layout}}
\end{itemize}

\end{enumerate}


\subsection{Typen}

\emph{Ausdrücke} bezeichnen \emph{Werte}

(Auswertung eines Ausdrucks versucht, ihn auf seine einfachste äquivalente
Form zu \emph{reduzieren}, also z.\,B. 

\begin{code}
3 + 4     => 7
abs(-2)   => 2
\end{code}
)

und jeder Wert hat einen \emph{Typ}, der wie folgt angegeben werden kann:

\begin{code}
   3 :: Int
True :: Bool
 abs :: Int -> Int
\end{code}

Solche \emph{Typdeklarationen} kann der Programmierer explizit anschreiben,
insbesondere bei der Einführung von Bezeichnern:

\begin{code}
  pi   ::  Float
  pi   =   3.14
area   ::  Float -> Float
area x =   pi * x * x
\end{code}

Er \emph{muß} es aber \emph{nicht} !

Trotzdem hat Haskell ein \emph{statisches} Typsystem (= Typ steht zur 
Compile-Zeit, also vor der Auswertung, fest):
Haskell betreibt neben Syntaxanalyse noch \emph{Typ-Inferenz}, d.\,h. 
erschließt den Typ von Ausdrücken aus Teilen und weist den Ausdruck
als \emph{fehlerhaft} zurück, falls kein vernünftiger Typ gefunden werden kann.

Empfehlung: verwende Typ deklarationen

\begin{itemize}
\item zur Dokumentation / Lesbarkeit
\item gegen Fehler (Haskell vergleicht Typdeklarationen mit erschlossenem Typ)
\end{itemize}

\noindent
Es gibt die üblichen \emph{Basistypen} wie

\begin{code}
Int, Float, Bool, Char
\end{code}

mit Elementen wie

\begin{code}
3, 3.14, True, 'A'
\end{code}

und Operationen wie

\begin{code}
+, *, .. , &&, ||, ..
\end{code}

und es gibt \emph{strukturierte} Typen wie z.\,B. \texttt{[Int]} oder
\texttt{[Char]} = Typen der Listen von Int- oder Char-Elemente mit
Elementen wie \texttt{[1,2,3], ['A', 'B', 'C']}.

\texttt{[]} = leere Liste,

Operator ``\texttt{:}'' zum Anfügen eines Elements \emph{vorne}:

\begin{code}
'A':['B','C']     ist     ['A','B','C']
\end{code}

und der Konkatenation ``\texttt{++}'':

\begin{code}
['A'] ++ ['B','C']
\end{code}

ist das selbe wie oben.

\noindent
Zusatz: \texttt{[Char]} ist dasselbe wie der Typ \texttt{String},
String-Elemente können wie üblich auch mit Anführungszeichen gebildet werden:
\texttt{ "{}ABC"{} }

\noindent
$\Longrightarrow$ Mehr über

\begin{tabular}{l@{ $\Rightarrow$ }l}
Basistypen               & Report, Literatur\\
Listen                   & späteres Kapitel\\
benutzerdefinierte Typen & späteres Kapitel
\end{tabular}

\noindent
Mit dem Hugs-Kommando ``\texttt{:type}'' kann man den Typ eines Ausdrucks erfragen:

\begin{code}
> :type 'A'
'A' :: Char
> :type "hallo"
"hallo" :: String
\end{code}

Das Ergebnis sieht aber manchmal anders aus als erwartet:

\begin{code}
> :type 3
3 :: Num a => a
> :type area
area :: Fractional a => a -> a
\end{code}

\begin{wichtig}
Ähnliches gilt für Meldungen bei Typfehlern!
\end{wichtig}

und verweist auf einen weiteren wichtigen Aspekt von Haskells Typ-System:

\begin{itemize}

\item Polymorphismus

= ein Haskell-Typ kann mit anderen Typen \emph{parametrisiert} sein.

\begin{description}

\item[Beispiel:]

Die Identitätfunktion ist für \emph{jeden} Typ sinnvoll; man darf
daher definieren

\begin{code}
id x = x
\end{code}

was den Typ

\begin{code}
id :: a -> a
\end{code}

mit Parameter ``\texttt{a}'' (Kleinbuchstaben!) ergibt, der für beliebige 
andere Typen steht, also möglich:

\begin{code}
id 3, id 'A', id [1,2,3]
\end{code}

neben parametrischem oder universellem Polymorphismus gibt es auch noch

\end{description}

\item Überladen (overloading, ad-hoc-Polymorphismus)

= das gewünschte Verhalten ist für mehrere, aber \emph{nicht} alle Typen
möglich und erfordert i.\,A. jeweils verschiedene Implementierungen.

\textbf{Beispiele:}
\begin{itemize}
\item Gleichheitsoperator ``==''

(``='' ist Definitionszeichen!)

und erfordert für Listen z.\,B. ganz andere Definition als für die diversen
Basistypen.

\item Zahlenbezeichner wie z.\,B. ``3'' stehen für verschiedene Zahlbereiche
(Int, Float, Genauigkeit), ähnlich arithmetische Operatoren wie ``+''.
\end{itemize}

Der Typinferenzmechanismus ermittelt deshalb einen parametrisierten
Typausdruck mit einer \emph{Einschränkung} des Parameters: der erlaubte
Typ muß zu einer Klasse gehören, die die im betrachteten Ausdruck vorkommenden Operationen usw. unterstützt.

\begin{description}
\item[Beispiel:] \ 

\begin{code}
> :type 3
3 :: Num a => a 
         -- lies: 3 hat Typ a, wobei a ein numerischer Typ ist

> :type area
area :: Fractional a => a -> a
         -- lies: area ist eine Funktion vom Typ a->a, wobei a ein
         -- Typ für "reelle" Zahlen ist, also die in der Definition
         -- von "area" steckende Multiplikation mit 3.14 verkraftet
\end{code}

\end{description}

$\Rightarrow$ mehr zum Thema später!

\begin{wichtig}
Polymorphismus \& Overloading nicht verwechseln mit den ebenso benannten
Dingen in Ada!
\end{wichtig}

\end{itemize}


\subsection{Typen von Funktionen}

\begin{itemize}

\item higher order functions

= Funktionen mit Funktionen als Argument und Resultat

z.\,B. (numerische) Differentiation:

\begin{code}
diff :: (Float -> Float) -> (Float -> Float)
diff f = g
  where g x = ( f (x + delta) - f x ) / delta
        delta = 0.001
\end{code}

( Obacht: Beispiel ist \emph{numerisch nicht} das Feinste! )

\begin{code}
> diff sin 0
1.0
> diff cos (pi/2)
-1.00005
>diff (diff cos) 0          -- 2. Ableitung
-1.07288
\end{code}

\begin{wichtig}
Beachte Bindekraft und Linksassoziierung von Funktionsanwendung!
\end{wichtig}

\begin{code}
diff sin 0     -- ist (diff sin) 0,
               -- und diff sin :: Float -> Float
               -- ( => :type Kommando!)
\end{code}

Sowas wie

\begin{code}
diff diff cos 0
\end{code}

wird deshalb gegliedert zu

\begin{code}
(diff diff) cos 0
\end{code}

und ergibt \emph{Typfehler!}

\item Currying

\begin{notiz}
( Konzept aus der Mathematischen Logik \& Grundlagenforschung;
erfunden von Schönfinkel, popularisiert durch Haskell Curry )
\end{notiz}

Funktionen mit \emph{mehreren} Argumenten werden meist aufgefaßt als
Funktionen mit \emph{Tupel} als Argument, z.\,B.:

\begin{tabbing}
Volumen :: \=(länge, breite, höhe) \= \kill

Volumen :: \>( \textbf{R $\times$ R $\times$ R} ) \>$\to$ \textbf{R} \\
           \>(länge, breite, höhe)       \>$\mapsto$ länge * breite * höhe
\end{tabbing}

Haskell benutzt andere und äquivalente Auffassung:

\begin{code}
volume :: Float->Float->Float->Float
volume l b h = l*b*h
\end{code}

deren besonderer Nutzen darin liegt, daß die Argumente sukzessive einzeln
kommen können d.\,h. \emph{partielle} Funktionsanwendung ist möglich
(und ergibt natürlich eine Funktion der \emph{restlichen} Argumente!):

\begin{code}
> volume 1 1
<< Function >>
> :type volume 1 1
volume 1 1 :: Float -> Float
\end{code}

Die durch partielle Anwendung resultierende Funktion läßt sich wie üblich
verwenden, z.\,B.:

\begin{code}
> diff (volume 1 1) 47.11
0.949451
\end{code}

und zur Bequemlichkeit auch mit einem Namen versehen, z.\,B.:

\begin{code}
volume_per_unitsquare = volume 1 1
\end{code}

\begin{description}
\item[anderes Beispiel:]
Differentiation mit variierbarer Genauigkeit:

\begin{code}
multi_diff :: Float -> (Float -> Float) -> (Float -> Float)
multi_diff d f x = (f (x+d)- f x) / d
\end{code}

dann kann man definieren:

\begin{code}
coarse_diff = multi_diff 10.0
fine_diff   = multi_diff 1.0e-3    -- nicht zu klein machen!!
\end{code}

und rechnen:

\begin{code}
> coarse_diff cos (pi/2)
0.0544021
> fine_diff cos (pi/2)
-1.00005
\end{code}

\end{description}

Damit partielle Anwendung funktioniert, müssen Funktionstypen 
\emph{nach rechts} assoziieren:

\begin{code}
        volume :: Float -> Float -> Float -> Float
-- ist:           Float -> (Float -> (Float -> Float))

    multi_diff :: Float -> (Float -> Float) -> (Float -> Float)
-- ist            Float -> ((Float -> Float) -> (Float -> Float))
\end{code}
\end{itemize}

Hier noch mal ausführliche Beispiele:

\begin{code}
-------------------------------POLYMORPHISM, list-type examples

Prelude> :type []
[] :: [a]
Prelude> :type (:)
(:) :: a -> [a] -> [a]
Prelude> :type 'a':[]
'a' : [] :: [Char]
Prelude> 'a':[]
"a"
Prelude> :type ['a','b','c']:[]
['a','b','c'] : [] :: [[Char]]
Prelude> ['a','b','c']:[]
["abc"]
Prelude> :type ['a','b','c']:['a','b','c']
ERROR: Type error in application
*** expression     : ['a','b','c'] : ['a','b','c']
*** term           : ['a','b','c']
*** type           : [Char]
*** does not match : Char
Prelude> :type ['a','b','c']:[['a','b','c']]
['a','b','c'] : [['a','b','c']] :: [[Char]]
Prelude> ['a','b','c']:[['a','b','c']]
["abc", "abc"]
Prelude> :type length
length :: [a] -> Int
Prelude> length []
0
Prelude> length ['a']
1
Prelude> length [1000, 10000]
2
Prelude> length ( ['a','b','c']:[['a','b','c']])
2


-------------------HIGHER ORDER FUNCTION EXAMPLE

tabulate :: Float->Float->Int->(Float->Float)->[Float]
tabulate start step times f
 |times <=0 = []  
 |otherwise = (f start):(tabulate (start+step) step (times-1) f)  

                            

Main> tabulate (-1) 0.2 11 sin
[-0.841471, -0.717356, -0.564642, -0.389418, -0.198669, -2.98023e-08, 
0.198669, 0.389418, 0.564642, 0.717356, 0.841471]


Main> :type diff
diff :: Fractional a => (a -> a) -> a -> a
Main> :type (diff cos)
diff cos :: Floating a => a -> a
Main> tabulate (-1) 0.2 11 (diff cos)
[0.8412, 0.716984, 0.564218, 0.38898, 0.198126, -0.000476837, -0.199199, 
-0.389874, -0.565052, -0.717699, -0.841737]


Main> let around_zero = tabulate (-1) 0.2 11 in around_zero sin
[-0.841471, -0.717356, -0.564642, -0.389418, -0.198669, -2.98023e-08, 
0.198669, 0.389418, 0.564642, 0.717356, 0.841471]
\end{code}



\subsection{Funktionsdefinitionen}

sind natürlich die Seele vom Geschäft und % FIXME
auf verschiedene Weise möglich, wobei man immer auf \emph{bereits vorhandenes
Material} aufbaut;

formell besteht eine Funktionsdefinition aus dem Definitionszeichen ``='',\\
einer \emph{linken} Seite, die den \emph{Namen} der Funktion und
(wenn zur Definition nötig) formalen Parametern besteht,\\
einer \emph{rechten} Seite, die (evtl. unter Benutzung der formalen Parameter)
ein \emph{Ausdruck} von entsprechendem Typ ist.

\begin{description}

\item[Beispiele:] \ 

\begin{code}
inc :: Int -> Int      -- Typdeklaration
inc x = x + 1          -- Funktionsdefinition
        -----          -- Ausdruck, der benutzt:
                       -- formalen Parameter x,
                       -- vordefinierte Funktionen x und 1

k_aus_n :: Int -> Int -> Int
k_aus_n k n = fac n `div` (fac k * fac (n-k))

negative :: Num(a) => a -> Bool
negative x = x < 0

is_zero :: Num(a) => a -> Bool
is_zero x = x==0
\end{code}

\end{description}

\emph{Keine formalen Parameter} benötigt man, wenn die neue Funktion
eigentlich eine alte ist \dots

\begin{code}
circle_area :: Float -> Float
circle_area = area

coarse_diff :: (Float -> Float) -> (Float -> Float)
coarse_diff = multi_diff 10.0         -- partielle Anwendung, vgl. vorher
\end{code}

\noindent
Im allgemeinen enthält die rechte Seite einer Definition eine

\begin{itemize}

\item Fallunterscheidung

= die einzelnen Definitionsfälle werden von \emph{"`Wächtern"'} (guards,
Boolesche Ausdrücke) gestützt;\\ %FIXME
es wird der (im Sinne der Aufschreibungsreihenfolge) erste Fall genommen,
dessen Wächter sich zu True errechnet.

\begin{description}
\item[Beispiele:] \ 

\begin{code}
max2 :: Int -> Int -> Int
max2 x y | x >  y = x
         | x <= y = y
\end{code}

dafür geht auch:

\begin{code}
max2 x y | x > y     = x
         | otherwise = y

max3 :: Int -> Int -> Int -> Int
max3 x y z | x>=y && x>=z = x
           | y>=x && y>=z = y
           | otherwise    = z
\end{code}

\end{description}

usw.

\item pattern matching

Beim Aufruf einer Funktion werden \emph{aktuelle} Parameter (=Ausdrücke,
Werte) an die Stelle der \emph{formalen} Parameter (bloße Bezeichner) 
gesetzt:

\begin{tabular}{lcc}
max2 & 17           & (2*3) \\
     & $\downarrow$ & $\downarrow$ \\
     & x            & y
\end{tabular}

Man kann dieses übliche "`matchen"' (auf einander beziehen) von formalen
und aktuellen Parametern auch noch \emph{verallgemeinern:}

Lasse zu, daß ein formaler Parameter ein \emph{Muster} (pattern) ist, d.\,h.
etwas \emph{Strukturiertes}.

Typische Beispiele bieten Listen-Datentyp:\\
eine Liste ist entweder die \emph{leere Liste} \texttt{[]}, \emph{oder} sie
hat ein {Listenelement} \texttt{x} gefolgt von einer \emph{Restliste} 
\texttt{xs}, d.\,h. hat den Aufbau \texttt{x:xs};\\
das nimmt man jetzt zur Definition;

\begin{description}
\item[Beispiel:] \ 

\begin{code}
sum_the_list :: [Int] -> Int
sum_the_list [] = 0
sum_the_list (x:xs) = x + sum_the_list xs
\end{code}

\end{description}

Beachte:

\begin{itemize}
\item für jeden pattern-Fall eigene Gleichung;

\item bei Anfang wird erst passende Gleichung (d.\,h. passendes Muster)
genommen; gibt es keine Übereinstimmung, resultiert ein Laufzeitfehler;

\item Witz an der Sache ist, daß in Verallgemeinerung der
formal/aktuell-Beziehung ein \emph{Zugriff auf Teile} (Konstituenten) des 
aktuellen Parameterwerts ermöglicht wird:\\
im Beispiel werden Kopf und Schwanz der Liste an \texttt{x} und \texttt{xs} 
gebunden:

\begin{tabular}{lclcll}
[ & 1             & , & $\underbrace{2, 3}$  & ] & aktuelle Parameter \\
  & $\downarrow $ &   & $\downarrow $        &   &                    \\
  & x             &   & xs                   &   & pattern-Teile
\end{tabular}

\end{itemize}

Was ist für patterns erlaubt?
\begin{itemize}
\item Variable (=formale Parameter) und Konstante (=numerische Literale, 
Char- , Bool-Elemente ),

\item Listen, von denen die Elemente wieder Patterns sind, also sowas wie 
\texttt{[True, b1, b2]},

\item mit ``:'' gebildete Listenausdrücke (siehe oben),

\item mit ``+'' gebildete arithmetische Ausdrücke der Form \texttt{n+k},
wobei \texttt{k} konstant und \texttt{n-k>=0} ist,

\item ähnlich: Ausdrücke der Form \texttt{k*n},

\item das wild-card-pattern ``\_'' auf das alles paßt
\end{itemize}

\begin{description}
\item[Beispiel:] \ 

\begin{code}
vorgaenger :: Int -> Int
vorgaenger 0     = 0             -- naja
vorgaenger (n+1) = n
\end{code}

dann folgt:

\begin{code}
> vorgaenger 77
76
> vorgaenger (2-3)    
Programm Error: {vorgaenger(-1)}
\end{code}

denn: (-1) läßt sich nicht in der verlangten Weise als n+1 darstellen, und
einen Fall für negative Werte gibt es nicht.


\item[Beispiel:]
für beliebige Listentypen:

\begin{code}
head (x:_)  = x           -- Rest der Liste interessiert nicht
                          -- Keine Definition für leere Liste!!

tail (_:xs) = xs          -- Kopf interessiert nicht,
                          -- nicht definiert für leere Liste!!
\end{code}

\end{description}


Manchmal will man eine Funktion konstruieren, ohne sie einem Bezeichner 
zuzuweisen, d.\,h. die Funktion bleibt anonym.

Beispiel: partielle Anwendung einer Funktion, also sowas wie
\texttt{volume 1 1}.

Weitere wichtige Möglichkeiten sind:

\item Lambda-Abstraktion \\
gegeben: ein Ausdruck \texttt{exp} und ein Variablenbezeichner \texttt{x}

dann: \texttt{$\backslash$x -> exp} ist diejenige Funktion, die einem
Wert v den Wert exp $v \atop x$ ( d.\,h. v ersetzt x in exp) zuweist.

\begin{description}
\item[Beispiel:] 

gegeben: $2.0 * x^2 - 1$

dann: \texttt{$\backslash$x -> (2.0 * x\^{}2 - 1.0)}

Das ist die Funktion mit Werten:

\begin{tabular}{c|c|c|c|c|c}
x    & \dots & -1 &  0 & 1 & \dots \\ \hline
Wert & \dots &  1 & -1 & 1 & \dots
\end{tabular}

also graphisch:

\setlength{\unitlength}{1cm}
\begin{picture}(6,4)

% Koordinatenachsen
\put(0.5,2){\vector(1,0){5}}
\put(3,0){\vector(0,1){4}}

% Einheiten
\multiput(1,1.9)(1,0){5}{\line(0,1){0.2}}
\multiput(2.9,1)(0,1){3}{\line(1,0){0.2}}

% Kurve von 2.0 * x^2 - 1.0 im Bereich [-1, 1]
\qbezier(3,1)(3.75,1)(4,3)
\qbezier(3,1)(2.25,1)(2,3)
\end{picture}

Natürlich kann man einen Bezeichner einführen wie z.\,B.

\begin{code}
f = {\bkslash}x -> 2.0 * x^2 - 1.0
\end{code}

aber es ist oft bequem, die unbenannte Funktion als Argument in 
"`higher order functions"' zu benutzen:

\begin{code}
> diff ({\bkslash}x -> 2.0 * x^2 - 1.0) 0
0.00202656
> diff ({\bkslash}x -> 2.0 * x^2 - 1.0) 1
4.00209
> diff ({\bkslash}x -> 2.0 * x^2 - 1.0) (-1)
-3.99792
\end{code}

\end{description}

usw.


\item Komposition von Funktionen

Mathematik: g$\circ$f heißt: erst f, dann darauf g anwenden,

also sowas wie "`2 Verarbeitungsschritte"' hintereinander:

% Stütze nötig, damit Box um f und g gleich Groß! FIXME
Ergebnis $\leftarrow$ \fbox{\rule[-1mm]{0mm}{4mm}g} $\leftarrow$ 
                      \fbox{\rule[-1mm]{0mm}{4mm}f} $\leftarrow$ Input

Die Haskell-Schreibweise für dieselbe Sache ist \texttt{g.f}

\begin{wichtig}
\emph{Wertebereich} von f muß zu \emph{Argumentbereich} von g passen!
\end{wichtig}

\begin{description}
\item[Beispiel:] 2. Ableitung:

\begin{code}
> (diff.diff) cos 0
-1.07288
\end{code}

denn: (-cos) $\leftarrow$ \fbox{diff} 
             $\leftarrow$ (-sin) $\leftarrow$ \fbox{diff} $\leftarrow$ cos

und - cos 0 = -1

\end{description}


\begin{wichtig}
\texttt{diff.diff cos 0} wird aufgefaßt als\\
\texttt{diff.((diff cos) 0)} wegen höchster Priorität der Funktionsapplikation!
\end{wichtig}

\begin{wichtig}
Funktions\emph{applikation} (bei higher order functions) und
Funktions\emph{komposition} \emph{nicht verwechseln!}
\end{wichtig}

% FIXME
\begin{code}
(diff.diff) cos 0
     |     |
     |     |--- Applikation: diff hat cos als Argument \emph{transformiert} cos
     |
     |--- Komposition: zweites diff wird \emph{nach} dem ersten diff, d.h.
          auf Ergebnis vom ersten diff angewendet.
\end{code}


Natürlich kann man dem Kind einen Namen geben, z.\,B.:

\begin{code}
> let diff2 = diff.diff in diff2 cos 0
-1.07288
\end{code}

\begin{description}

\item[Beispiel:] Komposition von \emph{Funktion} und \emph{inverser} Funktion gibt
Identität, z.\,B.: 

% FIXME
\begin{code}
sqrt . ({\bkslash}x -> x^2) = id  in R
 |      |
 |      |--- Quadratfunktion
 |
 |--- vordefinierte Wurzelfunktion
\end{code}

\begin{code}
> (sqrt.({\bkslash}x -> x^2)) 5
5.0
> (sqrt.({\bkslash}x -> x^2)) (-5)  -- stimmt nur für x>0
5.0
> diff (sqrt.({\bkslash}x -> x^2)) (-5)
-0.999927
\end{code}

\end{description}

\end{itemize}

\subsection{Operatoren}

= Funktionen mit \emph{2 Argumenten} in \emph{Infix}-Schreibweise

\emph{Operator-Bezeichner} werden durch Zusammenstellung von 1 oder mehr 
Sonderzeichen gebildet, 

klar: einige Sonderzeichen (-kombinationen) sind reserviert oder schon
belegt z.\,B.: ``\texttt{::}'', ``\texttt{=}'', ``\texttt{->}'' usw.

Man kann zwischen Operator-/Funktions-Schreibweise wechseln:

\begin{itemize}
\item Operator in Klammern

= Funktionsbezeichner für Präfix-Schreibweise, z.\,B.:

\begin{code}
> (+) 3 4
7
\end{code}

\item Funktionsbezeichner in backquotes ``\texttt{\`{}}''

= Operatorbezeichner für Infixschreibweise, z.\,B.:

\begin{code}
> 3 `div` 4
0
> 3 `max` 4
4
\end{code}

\end{itemize}

\noindent
Klammerungen:
es gibt 9 \emph{Präzedenzstufen}, z.\,B.: \\

\begin{tabular}{lll}
``\texttt{.}''    & Funktionskomposition & 9 \\
``\texttt{+}''    & Addition             & 6 \\
``\texttt{\&\&}'' & logisches und        & 3 \\
``\texttt{||}''   & logisches oder       & 2 \\
\end{tabular} \\

$\Rightarrow$ Literatur \\

\noindent
innerhalb einer Stufe gibt es \emph{Assoziativitätsregeln}:

\begin{itemize}
\item Assoziation nach \emph{links}:

z.\,B.: 8-5-1=(8-5)-1=2 und nicht 8-(5-1)=4

\item Assoziation nach \emph{rechts}:

z.\,B.: 2\^{}2\^{}3 = 2\^{}(2\^{}3) = 256 und nicht (2\^{}2)\^{}3 = 64

\item Operation \emph{ist assoziativ}, d.\,h. beliebig zu klammern:

z.\,B.: 3+2+1 = (3+2)+1 = 3+(2+1)

(Linksklammerung ist hier üblich)
\end{itemize}

$\Rightarrow$ Literatur

\begin{wichtig}
Benutzer kann selber Operatoren definieren und ihre Priorität und 
Assoziationsart in einer besonderen Deklaration festlegen, mehr dazu 
beim Thema "`Module"'.
\end{wichtig}


\subsection{Beispiel: Newton-Approximation}

Das Verfahren zur Ermittlung einer Nullstelle einer Funktion f: R$\rightarrow$R ist uns 
aus dem 1. Semester bekannt:

\texttt{$x_0$ := geeigneter Startwert}

\texttt{$x_{i+1}$ := $x_i$ - f($x_i$)/f\'{}($x_i$)}\\[2mm]


\setlength{\unitlength}{6mm}
\begin{picture}(8,9)

% Achsenabschnitte
\multiput(2,2.9)(1,0){5}{\line(0,1){0.2}}
\multiput(0.9,4)(0,1){5}{\line(1,0){0.2}}

% Tangente
\put(4,2){\line(1,2){2}}

% Achsenkreuz
\put(0,3){\vector(1,0){7}}
\put(1,1){\vector(0,1){8}}

% Kurve
\qbezier(0,2)(4,2)(5,4)
\qbezier(5,4)(5.5,5)(6,8)

\end{picture}


es gilt: $f'(x) \approx \frac{0-f(x_i)}{x_{i+1}-x_i}$ \\

\noindent
Das Verfahren ist wie geschaffen für \emph{imperative} Programmierung:

\begin{itemize}
\item \emph{Iteration} = Serie von Schritten, bis akzeptable Näherung gefunden

\item \emph{Programmvariable} = nehmen sich ändernde Werte von x auf
\end{itemize}

also interessant, ob man sowas --- und zwar gut! --- \emph{funktional}
erledigen kann! \\

\noindent
Wir erinnern uns:

\begin{itemize}
\item Iteration läßt sich durch Rekursion ersetzen
\item wobei Zwischenergebnisse als Resultate der Funktionsergebnisse
"`unterwegs"' anfallen.
\end{itemize}

\noindent
Daher die offensichtliche Lösung:

\begin{code}
newton :: (Float->Float)->Float->Float
newton f x
   |abs(f x) < 0.001 = x  -- Feierabend wenn gut genug
   |otherwise        = newton f (x - f x / diff f x) -- weiter
\end{code}

Anwendung z.\,B. so:

\begin{code}
Main> newton ({\bkslash}x->x^2-2) 10  --loest x^2-2 = 0, d.h. Wurzel 2, Start bei 10
1.41454
\end{code}

Hat man erst eine Programmieraufgabe gelöst, so sollte man gleich fragen,
ob sich die Lösung \emph{verallgemeinern} läßt, d.\,h. gibt es hier eine
\emph{Struktur}, ein \emph{Muster}, das \emph{mehrfach} angewendet werden
kann? \\

\noindent
\emph{Bestandteile} der Lösung sind:

\begin{itemize}
\item ein Ausgangswert: \texttt{x}
\item eine den aktuellen Wert verbessernde Berechnung: 
      \texttt{(x - f x / diff f x)}
\item ein Wiederholungsmechanismus: rekursiver Aufruf
\item ein Abbruchkriterium
\end{itemize}

\noindent
Idee:

Mache aus dem Wiederholungsmechanismus eine Funktion, die die drei anderen
Bestandteile als Parameter hat!

Daher definiere:

\begin{code}
until :: (a->Bool)->(a->a)->a->a
           |          |     |  |--- Ergebnis
           |          |     |--- Startwert
           |          |--- Verbesserung
           |--- Abbruchkriterium
\end{code}

Und natürlich a = \emph{Typvariable}, d.\,h. egal, in welchem Wertebereich
wir arbeiten, also \emph{polymorphe} Funktion.

\begin{code}
repeat_until::(a->Bool)->(a->a)->a->a
repeat_until crit change x
   |crit x    = x                                   --zufrieden
   |otherwise = repeat_until crit change (change x) --weiter
\end{code}

\begin{description}
\item[Einfaches Anwendungsbeispiel:] \ 

\begin{code}
Main> repeat_until even pred 10
10
Main> repeat_until even pred 11
10
\end{code}

Wobei die Standardfunktionen

\begin{code}
even :: Int -> Bool     -- "ist gerade"
pred :: Int -> Int      -- "Vorgänger"
\end{code}

vorhanden sind.

\end{description}

\noindent
Jetzt damit zurück zu Newton:

\begin{code}
newton :: (Float->Float)->Float->Float
newton f x = repeat_until n_crit n_change x
   where n_crit x = abs(f x) < 0.001
         n_change x = x - f x / diff f x
\end{code}

\begin{description}
\item[Anwendung für Quadratwurzelberechnung:] \ 

\begin{code}
Main> newton ({\bkslash}x->x^2-2) 10
1.41454
Main> newton ({\bkslash}x->x^2-25) 10
5.0
Main> newton ({\bkslash}x->x^2-80) 10
8.94427
\end{code}

\end{description}

usw.

\begin{itemize}
\item Man kann die Suche noch flexibler machen, insbesondere
   \emph{bessere Abbruchkriterien} einführen, die auf \emph{Vergleich} von
   2 (oder mehr) der \emph{aufeinanderfolgenden Näherungswerte} beruhen;

   $\Rightarrow$ Kapitel 3: Listen

\item Man kann Nullstellenberechnung auch benutzen, um die 
   \emph{inverse Funktion} zu einer Funktion f numerisch zu ermitteln:

   \[f^{-1}(y) = x \qquad\mbox{gdw.}\qquad f(x)-y = 0 \]

Das leistet die folgende Definition:

\begin{code}
inverse:: (Float->Float)->Float->Float->Float
inverse f y x = newton g x
   where g x = f x - y    
\end{code}

Einfache Anwendungen sind wieder Wurzelprobleme:

\begin{code}
Main> inverse ({\bkslash}x->x) 2 10
2.0
Main> inverse ({\bkslash}x->x^2) 2 10
1.41454
Main> inverse ({\bkslash}x->x^3) 2 10
1.25993
Main> inverse ({\bkslash}x->x^4) 2 10
1.18925
Main> inverse ({\bkslash}x->x^10) 2 10
1.07179
\end{code}

usw.
\end{itemize}

\begin{description}
\item[Beachte:] \ 

Anwendung der Newton-Iteration hat ihre mathematischen Grenzen, \emph{und}
man muß sich für wirklich gute Ergebnisse auch noch in der numerischen
Mathematik auskennen und Sorgfalt hinsichtlich Startwerten,
Abbruchkriterien, genaue Formulierungen des Iterationsschritts \dots
walten lassen!

\end{description}


\subsection{Auswertung von Ausdrücken}

= Reduktion auf die einfachste äquivalente Form als Antwort

dazu: verwende "`eingebaute"' Semantik für primitive Operationen \emph{und}
die vom Programmierer gelieferten Definitionen, nämlich: ersetze linke
Seite einer definierenden Gleichung durch rechte Seite.

\begin{description}
\item[Beispiel:] \ 

gegeben:

\begin{code}
pi = 3.14
area x = pi * x * x
\end{code}

dann:

\begin{code}
   area (9+1)
=> area 10        Semantik "+"
=> pi * 10 * 10   Definition "area"
=> 3.14 * 10 * 10 Definition "pi"
=> 31.4 * 10      Semantik "*"
=> 314            Semantik "*"
\end{code}

(dabei angenommen, was stimmt, daß Folgen von ``*'' unter Assoziation nach
\emph{links} ausgewertet werden)

\begin{wichtig}
Das ist \emph{nicht die einzig} mögliche Reduktionsfolge!
\end{wichtig}


\item[Alternative:] \ 

\begin{code}
   area (9+1)
=> pi   * (9+1) * (9+1)  Definition "area"
=> 3.14 * (9+1) * (9+1)  Definition "pi"
=> 3.14 * 10 * (9+1)     "+"
=> 31.4 * (9+1)          "*"
=> 31.4 * 10             "+"
=> 314                   "*"
\end{code}

\end{description}

Im ersten Beispiel wird zuerst der \emph{innere} Teilausdruck ``(9+1)'' 
ausgewertet, während im zweiten Beispiel die Auswertung \emph{von außen}
nach \emph{innen} geschieht; 
man spricht (bei konsequenter Anwendung der Vorgehensweisen) von
"`innermost"' und "`outermost"' Strategie.

\begin{wichtig}
\emph{Haskell} verwendet \emph{"`outermost"'} mit dem wichtigen Zusatz, daß
\emph{Mehrfachvorkommen desselben} Teilausdrucks nur \emph{einmal}
ausgewertet werden.
\end{wichtig}

\begin{description}
\item[also im Beispiel:] \ 

\begin{code}
   area (9+1)
=> pi * (9+1) * ( )
          >------^
=> 3.14 * (9+1) * ( )
            >------^
=> 3.14 * 10 * 10
=> ...
\end{code}

\end{description}

Outermost-Reduktion mit dieser Optimierung heißt auch 
\emph{"`lazy evaluation"'}: Ein Teilausdruck wird erst ausgewertet, wenn es 
wirklich nicht mehr anders geht, und dann auch nur einmal.\\
$\Rightarrow$ möglich, daß Teilausdruck gar nicht ausgewertet,\\
$\Rightarrow$ möglich, daß das Scheitern einer Berechnung vermieden wird!

\begin{description}
\item[Beispiel:] \ 

\begin{tabular}{rl}
definiere: & \texttt{first\_of\_two x y = x} \\
     dann: & \texttt{first\_of\_two 1 (1 `div` 0)} \\
           & \texttt{=> 1     -- outermost!}
\end{tabular}

\end{description}


Bei innermost gäbe es hier einen Laufzeitfehler!

ähnlich: nicht-terminierende Teil-Berechnung.

\begin{description}
\item[Welche Strategie ist besser?] \ 

\emph{Keine} eindeutige Antwort; verschiedene Programmiersprachen verhalten 
sich verschieden:

innermost (auch: "`eager evaluation"'):

Lisp-Dialekte, ML (funktionale Sprachen)
imperative Sprachen!

mit kleinen Ausnahmen, z.\,B.:

\begin{code}
if ... then ... else ...
... and then ...
... or else ...
\end{code}


\item[Theorie sagt:] \ 

Wenn innermost ein Ergebnis liefert, dann liefert outermost \emph{dasselbe}
Ergebnis -- aber es kann sein (siehe oben), daß \emph{nur} outermost
ein Ergebnis liefert!


\begin{itemize}
\item outermost Vorteile:

\begin{quote}
Erlaubt gewisse Programmstrukturen, die mit unendlichen Datenstrukturen
( $\approx$ nicht terminierende Berechnungen) arbeiten.
\end{quote}

\item outermost Nachteile:

\begin{quote}
Implementierung schwieriger und aufwendiger
\end{quote}

\end{itemize}


\item[noch ein damit zusammenhängender Begriff:] \ 

weil Auswertung eines Ausdrucks scheitern kann, ist es bequem (für theoretische
Überlegungen), alle Wertebereiche durch einen besonderen Wert zu ergänzen:

\begin{tabular}{cl}
$\bot$ & = "`undefiniert"' = "`bottom"' \\
       & steht für Laufzeitfehler oder Nichtterminierung
\end{tabular}

dann:

Funktion f heißt \emph{strikt} \quad gdw. \quad \texttt{f} $\bot = \bot$.

arithmetische Operationen sind immer strikt --- klar, 3 mal undefiniert is
undefiniert ---, aber bei lazy evaluation gibt es auch nicht strikte 
Funktionen:

\begin{description}
\item[Beispiel:] konstante Funktionen wie z.\,B.:

\begin{code}
three x = 3
\end{code}

dann:
\begin{code}
three (1/0)
=> 3         -- outermost!
\end{code}


\begin{code}
all_ints_from :: Int -> [Int]
all_ints_from x = x : all_ints_from(x+1)

first_even :: [Int] -> Int
first_even x:xs
        | even x    = x
        | otherwise = first_even xs
\end{code}

\end{description}

\end{description}


\subsection{Input / Output}

lassen sich nur schwer dem Grundprinzip "`Funktionsauswertung"' unterordnen.

\begin{description}
\item[Beispiel:] \ 

Interaktion mit Benutzer durch Ausgabe von Ergebnissen und Aufforderung
zu weiterer Eingabe.
\end{description}

Eine saubere Lösung benötigt erhebliche theoretische/konzeptuelle 
Vorbereitung; hier Beschränkung auf Rezept für Teilproblem: \\

\noindent
Wie kriegt man Ergebnis einer Berechnung in sinnvoll formatierter Weise 
ausgedruckt?

\begin{enumerate}
\item die üblichen Datentypen gehören zu einer Typklasse \texttt{Show}
und bieten eine Funktion \texttt{show::(Show a) => a -> String}, die 
Wert (Element des Datentyps) in einen String umwandelt;

\begin{wichtig}
Diese Funktion wird von Hugs zur Ausgabe von Ergebnissen benutzt.
\end{wichtig}

\begin{wichtig}
Es gibt Typen, die nicht zur Klasse \texttt{Show} gehören, insbesondere 
Funktionstypen.
\end{wichtig}

\begin{wichtig}
Führt man selber neue Datentypen ein ($\Rightarrow$ später), so sollte man
sich um eine \texttt{show}-Funktion kümmern.
\end{wichtig}

\item Hugs benutzt \texttt{show}-Funktionen, gibt aber dann Antworten 
üblicherweise nicht in Form von Haskell-String-Bezeichnern, sondern eben
die Zeichenreihe selbst:

\begin{code}
> fac 3
6
\end{code}

Ausnahme:
\begin{quote}
Werte vom Typ String werden so ausgegeben, wie sie auch in der 
Programmiersprache auftreten, nämlich in Anführungszeichen:

\begin{code}
> "ABC"
"ABC"
\end{code}
\end{quote}

\begin{wichtig}
Differenz zu älteren Hugs-Versionen oder Gofer ($\Rightarrow$ Vorsicht bei
gebrauch von Literatur)
\end{wichtig}

\item zum Zeichenvorrat Char gehören neben druckbaren Zeichen auch 
\emph{Steuerzeichen}, 
insbesondere \emph{newline} Symbol: \texttt{'$\backslash$n'}

(Bemerkung: backslash $\backslash$ dient als Fluchtsymbol, andere 
Verwendung:

% FIXME!
\begin{tabular}{c@{\quad $\widehat{=}$ \quad }l}
\texttt{'$\backslash\backslash$'} & backslash \\
\texttt{'$\backslash$\'{}'}       & single quote \\
\texttt{'$\backslash$"\'{}}       & double quote )
\end{tabular}

Mann kann dan Text \emph{formatieren} wie z.\,B.:

\begin{code}
"dies ist {\bkslash}neine neue Zeile "
\end{code}

was man mit Hilfe des \emph{Konkatenationsoperators} \texttt{++}
vielleicht sinnfälliger schreiben kann als

\begin{code}
"dies ist {\bkslash}n" ++ "eine neue Zeile"
\end{code}

\begin{wichtig}
Aber: wegen vorherigem Punkt hilft das noch nicht viel: 

Hugs druckt gnadenlos den String:

\begin{code}
> "dies ist {\bkslash}n" ++ "eine neue Zeile"
"dies ist {\bkslash}neine neue Zeile"
\end{code}

d.\,h. interpretiert \texttt{$\backslash$}n \emph{nicht}!
\end{wichtig}

\item Vernünftig wird das Resultat durch Vorschalten der Funktion

\begin{code}
putStr :: String -> IO()
\end{code}

nämlich:

\begin{code}
> putStr("dies ist {\bkslash}n" ++ "eine neue Zeile")
dies ist
eine neue Zeile
\end{code}

\begin{wichtig}
Sorry: Genaue Diskussion des "`Wertebereichs"' dieser "`Funktion"' ist hier
nicht möglich.
\end{wichtig}

\begin{itemize}
\item approximative Vorstellung:

putStr liefert als Ergebnis (Wert) eine \emph{Aktion}, d.\,h. \texttt{IO()}
und verwandte Typen beinhalten Aktionen, und Wiedergabe von sowas durch Hugs 
ist gleich Ausführung der Aktion.

\item Anwendung von putStr und ähnlichen Funktionen nur auf dem 
\emph{top level} von Ausdrücken möglich, also \emph{nicht} innerhalb von
normalen Ausdrücken mit normalen Werten!

(d.\,h. man kann anders als in Ada nicht \emph{während} der Auswertung einer
Funktion wie \texttt{fac :: Int->Int} mal \'{}was ausdrucken!)
\end{itemize}

\end{enumerate}

\begin{description}
\item[Beispiel:] \ 

Wir machen die Fakultätsfunktion "`fehlertolerant"' dadurch, daß sie für 
negative Argumente eine entsprechende Meldung erzeugt.

Dazu: ändere Fakultätsfunktion so, daß sie Zeichenreihe als Ergebnis hat:

\begin{code}
fac:: Int->Int
fac 0 = 1
fac n = n*fac (n-1)

fault_tolerant_fac::Int->String
fault_tolerant_fac n
   |n >= 0     = show(fac n)
   |otherwise  = ">>>: fac nicht definiert {\bkslash}n"++
                 "     fuer "++ (show n)


Main> fault_tolerant_fac 3
"6"
Main> fault_tolerant_fac (-3)
">>>: fac nicht definiert {\bkslash}n     fuer -3"
Main> putStr (fault_tolerant_fac (-3))
>>>: fac nicht definiert
     fuer -3
\end{code}

\end{description}

Für dieses Beispiel gibt es eine bessere Lösung: Haskell hat Vorkehrungen
für Ausnahmebehandlung, z.\,B.:

\begin{code}
error :: String->a
\end{code}


\begin{wichtig}
Dies ist auch wieder eine Funktion, die auf eine Aktion hinausläuft: 
\emph{Abbruch} der Auswertung, aber: vorher wird die als Argument
gegebene Zeichenreihe ausgedruckt.

(error hat den polymorphen Ergebnistyp a, damit man die Funktion in jeden
Zusammenhang einfügen kann)
\end{wichtig}

\begin{code}
fault_tolerant_fac::Int->Int
fault_tolerant_fac n
   |n >= 0     = fac n
   |otherwise  = error (" fac nicht definiert fuer " ++ (show n))


Main> fault_tolerant_fac (-3)

Program error:  fac nicht definiert fuer -3
\end{code}

Wirkung von error:
\begin{enumerate}
\item Abbruch (= Program error)
\item Ausgabe des vom Programmierer vorgesehenen String
\end{enumerate}



\chapter{Listen}


\section{Elementares}

\begin{itemize}
\item Listen sind \emph{linear} angeordnete \emph{Kollektionen} von Werten
\emph{desselben} Typs.

\begin{wichtig}
Unterschied zum Mengenbegriff:
\begin{code}
[1] /= [1,1],  [1,2] /= [2,1]
\end{code}
\end{wichtig}

\item Listen können über \emph{jeden} Typ gebildet werden:

\begin{code}
[] :: [a]   -- leere Liste, gehört zu jedem Listentyp (polymorph)

[1,2,3] :: Num a => [a]              -- Liste von Zahlen

[[1], [2,3]] :: Num a => [[a]]       -- Liste von Listen von Zahlen

[[], [2,3]] :: Num a => [[a]]        -- [] als leere Zahlenliste

[sin, cos] :: Floating a => [a->a]   -- Liste von reelen Funktionen

[coarse_diff, fine_diff] :: [(Float->Float)->Float->Float]
                                     -- Liste von higher order functions
\end{code}

\begin{wichtig}
\begin{code}
1 /= [1]
\end{code}

Element ungleich einelementige Liste (singleton list)!
\end{wichtig}

\item Listen sind wichtige Datenstruktur in gesamter Informatik, aber in
funktionaler Programmierung noch größere Bedeutung als in imperativer
Programmierung; 

insbesondere: lazy evaluation erlaubt Arbeit mit \emph{unendlichen} Listen!

\item Listen sind gut verstandener mathematischer Gegenstand mit vielen 
nützlichen Gesetzen für einschlägige Operationen und Funktionen.

zB:

\begin{quote}
R.~Bird:\\
"`An introduction to the theory of lists"',\\
Oxford Programming Research Group report PRG-56, 1986\\
\end{quote}


\item Listen können \emph{aufgebaut} und in \emph{eindeutiger} Weise
\emph{zerlegt} werden durch:

\begin{code}
[] :: [a]  -- leere Liste, Basis aller Konstruktionen

(:) :: a->[a]->[a]  -- Anfügen eines Elements am Kopf der Liste
                    -- ("cons" = "construct"-Operation)
\end{code}

\begin{description}
\item[zB:] \ 

\begin{code}
3:[]
2:(3:[])
1:(2:(3:[]))
\end{code}

\end{description}


\begin{wichtig}
(:) assoziiert \emph{rechts}, also:
\begin{code}
1:2:3:[]  ==  1:(2:(3:[]))
\end{code}
\end{wichtig}

\begin{wichtig}
Konstruktion / Zerlegung mit (:) ist Grundlage aller Definitionen 
einschlägiger Operationen / Funktionen.
\end{wichtig}

\item Es gibt mehrere \emph{notationelle Kurzformen:}

\begin{itemize}

\item \textbf{Aufzählung:}

\begin{code}
[1,2,3] == 1:2:3:[]
\end{code}

Sonderfall für Strings:

\begin{code}
"abc" == ['a', 'b', 'c']
      == 'a':'b':'c':[]
\end{code}


\item \textbf{Intervalle:} 

\begin{code}
[2..5]   == [2,3,4,5]  -- Schritte von +1
[5..2]   == []         -- Schritte von +1
[5,4..2] == [5,4,3,2]  -- Schritte von -1
\end{code}

ähnlich:

\begin{code}
['a','c'..'f'] == "ace"
\end{code}

\begin{wichtig}
Beachte:
\begin{code}
[0.0,0.2..1.4] == [0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2]
       -- Feierabend, wenn Obergrenze nicht exakt getroffen wird
       -- (Float-Arithmetik!)

[0.2,0.2..1.4] == [0.2,0.2,0.2,0.2......
       -- Schrittweite von 0!
\end{code}
\end{wichtig}

\item \textbf{Listen-Komprehension:} (analog: Mengenkomprehension)

Sei \texttt{l = [1,2,3]}\\
dann \texttt{[ 2*x | x<-l ] == [2,4,6]}

$\Rightarrow$ genauere Betrachtung später...

\end{itemize}
 
\item viele \emph{Standardfunktionen / -operationen}

Definition abgestützt auf [] und (:) und pattern matching.

zB kennen wir schon:

\begin{code}
length :: [a] -> Int   -- Länge der Liste
head   :: [a] -> a     -- Kopfelement
tail   :: [a] -> [a]   -- Rest
                       -- head und tail sind partielle Funktionen,
                       -- Fehler falls Liste leer!
\end{code}

andere Beispiele:


\begin{itemize}
\item \textbf{Konkatenation} (join, append, Vereinigung)

zB:

\begin{quote}
\begin{code}
[1,2] ++ [1,3] == [1,2,1,3]
[] ++ [1,2] == [1,2]
[1,2] ++ [] == [1,2]
\end{code}
\end{quote}

also:

\begin{quote}

\begin{code}
(++) :: [a]->[a]->[a]
[] ++ ys     = ys
(x:xs) ++ ys = x : (xs++ys) 
\end{code}
\end{quote}

\begin{description}
\item[Beispiel:] Listenumkehr:

\begin{code}
reverse :: [a]->[a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]
\end{code}

\end{description}


(++) ist \emph{assoziative} Operation mit \emph{neutralem} Element [], also:

\begin{code}
([1]++[2])++[3] == [1,2,3] == [1]++([2]++[3])
\end{code}

In Haskell konventionell Assoziirung nach rechts:

\begin{code}
[1]++[2]++[3] == [1]++([2]++[3])
\end{code}

\begin{wichtig}
(:) und (++) nicht verwechseln; Typfehler bei:

\begin{code}
[1]:[2,3]
1++[2,3]
\end{code}
\end{wichtig}


\item \textbf{Konkation, Form 2} ("`flatten"')

wirkt auf \emph{Listen} von \emph{Listen}:

\begin{code}
concat [[1,2,3],[4,5],[],[6]] == [1,2,3,4,5,6]
\end{code}

also:

\begin{code}
concat :: [[a]]->[a]
concat []     = []
concat (x:xs) = x ++ concat xs
\end{code}

\begin{wichtig}
Beachte Typen in dieser Definition:

\begin{code}
[] :: [[a]]
[] :: [a]
x  :: [a]
xs :: [[a]]
\end{code}
\end{wichtig}


\item \textbf{Teil-Listen:}

\begin{code}
take, drop :: Int->[a]->[a]
take 0 _  = []
take _ [] = []
take (n+1) (x:xs) = x:take n xs

drop 0 xs = xs
drop _ [] = []
drop (n+1) (x:xs) = drop n xs


-- Anwendung zum Beispiel:
> take 2 "abc"
"ab"
> take 5 "abc"
"abc"

> drop 2 "abc"
"c"
> drop 5 "abc"
""
\end{code}

\item \textbf{Enthalten sein:}

\begin{code}
elem :: a->[a]->Bool
elem _ [] = False
elem e (x:xs) = x==e || elem e xs

-- Anwendung zum Beispiel:
> elem 'a' "abc"
True
> elem 'x' "abc''
False
\end{code}


\end{itemize}


\end{itemize}


$\Rightarrow$ \emph{Standard Prelude} A1, Report Seite 96 ff. enthält
viele weitere Definitionen, einiges daraus später!

\begin{itemize}
\item Dieser Teil ist auch ohne "`höhere"' Haskell-Kenntnisse fast 100\%
verständlich $\Rightarrow$ lesen!

\item allgemeiner Aufbau als Haskell-Modul:

\begin{code}
module PreludeList     -- Modulkopf
   (head, tail, ...)   -- Verzeichnis der nach aussen angebotenen Dienste
                       -- (Exportliste vgl. Spezifikationsteil von Ada Paketen)
  where                -- hier geht's los

import ...             -- Verzeichnis der von anderswo importierten Dienste
                       -- (vgl. Ada "with clause")

infix ...              -- "fixity declarations" d.h. Deklaration von 
                       -- Präzedenz und Assoz. der im Modul definierten
                       -- Operatoren

...                    -- jetzt die Definitionen ("Implementierung")
\end{code}

\end{itemize}

Beispiel PreludeList aus dem Standard-Prelude:

\begin{code}
   --  A.1  Prelude PreludeList

   -- Standard list functions
   module PreludeList (
       head, last, tail, init, null, length, (!!),
       foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
       iterate, repeat, replicate, cycle,
       take, drop, splitAt, takeWhile, dropWhile, span, break,
       lines, words, unlines, unwords, reverse, and, or,
       any, all, elem, notElem, lookup,
       sum, product, maximum, minimum, concatMap,
       zip, zip3, zipWith, zipWith3, unzip, unzip3)
     where

   import qualified Char(isSpace)

   infixl 9  !!
   infix  4  `elem`, `notElem`

   -- head and tail extract the first element and remaining elements,
   -- respectively, of a list, which must be non-empty.  last and init
   -- are the dual functions working from the end of a finite list,
   -- rather than the beginning.
   head             :: [a] -> a
   head (x:_)       =  x
   head []          =  error "PreludeList.head: empty list"

   last             :: [a] -> a
   last [x]         =  x
   last (_:xs)      =  last xs
   last []          =  error "PreludeList.last: empty list"

   tail             :: [a] -> [a]
   tail (_:xs)      =  xs
   tail []          =  error "PreludeList.tail: empty list"

   init             :: [a] -> [a]
   init [x]         =  []
   init (x:xs)      =  x : init xs
   init []          =  error "PreludeList.init: empty list"

   null             :: [a] -> Bool
   null []          =  True
   null (_:_)       =  False

   -- length returns the length of a finite list as an Int.
   length           :: [a] -> Int
   length []        =  0
   length (_:l)     =  1 + length l
   ...
\end{code}

\section{Beispiel: Sortieren durch Einfügen}

das Verfahren ist uns wohlbekannt:
\begin{quote}
sortiere Liste durch wiederholtes ordnungsgerechtes Einfügen.
\end{quote}
hier die Haskell Definitionen:

\begin{code}
into :: Ord a => a->[a]->[a]     -- Sortieren braucht Ordnungsrelation auf
                                 -- Elementtyp!
into x [] = [x]
into x (y:ys) 
       |x <= y    = x:y:ys       -- aufsteigend!
       |otherwise = y:into x ys 

iSort :: Ord a => [a]->[a]
iSort [] = []
iSort (y:ys) = into y (iSort ys)

-- Anwendung zum Beispiel:
> into 3 [1,5,7,12]
[1,3,5,7,12]
> into 'a' "Computer"
"Caomputer"
> into "xx" ["aa", "zz"]
["aa","xx","zz"]           -- Strings und allgemein Listen von Elementen mit
                           -- Ordnungsrelation, sind in Haskell 
                           -- lexikographisch geordnet!
> iSort [2,-9,67,-3,0,11]
[-9,-3,0,2,11,67]
> iSort [cos 0, cos 1, cos 2, cos 3]
[-0.989992, -0.416147, 0.540302, 1.0]
\end{code}

\begin{wichtig}
Man beachte die Segnungen von overloading und polymorphism!
\end{wichtig}

\begin{wichtig}
Kontrollfrage: was gibt
\begin{code}
> iSort [cos,sin]  ?
> iSort []         ?
\end{code}
\end{wichtig}



\section{Beispiel: "`Datenbank"'}
Zur Verwaltung der Hardware des Institus wird eine Liste geführt, die aus 
Paaren des Formats \texttt{(<Rechnertyp>, <Raum>)} besteht.

Lösung hier ist sehr primitiv, soll nur Arbeit mit Listen illustrieren.

(natürlich kennt Haskell auch Aufzählungstypen, natürlich kann man auch
einen Ordnungsbegriff %FIXME
für die Listenelemente einführen usw. usf. \dots )

\begin{code}
-------------------------------------Liste von Rechnern mit Aufstellungsort

type Room = String                           --Typ-Synonyme fuer Lesbarkeit
type Hardware = String
type HwList =[(Hardware,Room)]

example_list =                                                   --Beispiel
               [("PC","T01"),
                ("PC","Lab1"),("PC","Lab1"),("PC","Lab1"),
                ("PC","Lab2"),("Sun","Lab2"),("Sun","Lab2")]

                                                             --Aufbau/Abbau
insert, delete:: Hardware->Room->HwList->HwList
insert h r hwl = (h,r):hwl
delete h r [] = []               --keine Wirkung wenn (h,r) nicht vorhanden
delete h r ((h1,r1) : rest)
       |h1 == h && r1 == r = rest
       |otherwise          = (h1,r1) : delete h r rest

                                --Funktionen fuer Anfragen, Aenderungen etc
locations:: Hardware->HwList->[Room]  --Ergebnis enthaelt Mehrfachvorkommen
locations h [] = []
locations h ((h1,r1) : rest)
       |h1 == h    = r1 : (locations h rest)
       |otherwise  = locations h rest

how_many:: Room->HwList->Int
how_many r [] = 0
how_many r ((h1,r1) : rest)
       |r1 == r   = 1 + how_many r rest
       |otherwise = how_many r rest

replace:: Hardware->Hardware->HwList->HwList
replace h h' [] = []
replace h h' ((h1,r1) : rest)  = entry : replace h h' rest
                          where entry |h1 == h   = (h',r1)
                                      |otherwise = (h1,r1)


-- Beispielanwendungen der definierten Funktionen
> insert "Sun" "T01" []
[("Sun", "T01")]
> locations "Sun" example_list
["Lab2","Lab2"]
> locations "Sun" (replace "Sun" "Moon" example_list)
[]
> how_many "Lab2" (delete "PC" "Lab2" example_list)
2
> how_many "PC" (delete "PC" "Lab2" example_list)
0       -- Quatsch, das kommt davon, wenn man mit Typsynonymen arbeitet!!
\end{code}


\section{Higher order functions (HOFs) für Listen}

\begin{wichtig}
Ein gut sortierter Werkzeugkasten voll HOFs erlaubt, typische Aufgaben 
\emph{ohne} explizite Programmierung des Listendurchlaufs (Rekursion,
pattern matching) zu lösen.
\end{wichtig}

\begin{wichtig}
Natürlich ist alles polymorph um universelle Anwendung zu ermöglichen!
\end{wichtig}


\begin{itemize}
\item \emph{map} wendet eine Funktion an auf jedes Listenelement:

\begin{code}
map:: (a->b)->[a]->[b]
map f [] = []
map f (x:xs) = f x : map f xs

> map even [1..10]
[False,True,False,True,False,True,False,True,False,True]
\end{code}

\item \emph{fold}-Funktionen fassen Listenelemente zusammen, indem sie eine
geeignete Operation "`dazwischen setzen"'; es gibt mehrere Arten:

\begin{code}
foldr:: (a->b->b)->b->[a]->b
foldr op start []      = start
foldr op start (x:xs)  = x `op` (foldr op start xs)

foldl:: (a->b->a)->a->[b]->a
foldl op start []      = start
foldl op start (x:xs)  = foldl op (start `op` x) xs
\end{code}

also:

\texttt{foldr op start [$x_1$\dots$x_n$] = $x_1$ `op` ($x_2$ `op` (\dots($x_n$ `op` start)\dots)}

\texttt{foldl op start [$x_1$\dots$x_n$] = (\dots(start `op` $x_1$) `op` $x_2$)\dots) `op` $x_n$}

\begin{code}
> foldr (+) 0 [1..10]
55
> foldl (+) 0 [1..10]
55
                        -- jetzt Unterschied!

> foldr (-) 0 [1..10]
-5                      -- 1-(2-(...10-0)...)
> foldl (-) 0 [1..10]
-55                     -- (...(0-1)-2)...)-10
\end{code}

Will man \emph{nur} die Elemente der Liste zusammenfassen, so benötigt man für
foldr und foldl ein \emph{neutrales} Element der anzuwendenden Operation
als Startwert (Basiswert):

\begin{code}
sum:: [Int]->Int
sum = foldr (+) =
\end{code}

es geht auch ohne:

\begin{code}
foldr1 :: (a->a->a)->[a]->a
foldr1 op [x]    = x
foldr1 op (x:xs) = x `op (foldr1 op xs)
\end{code}

also:
\texttt{foldr op start [$x_1$\dots$x_n$] = $x_1$ `op` ($x_2$ `op` (\dots($x_{n-1}$ `op` $x_n$)\dots)}

\begin{wichtig}
Liste darf nicht leer sein!
\end{wichtig}

analog: foldl1

\begin{code}
> foldl1 max [1..10]
10      -- 0 nicht neutrales Element für max, da Liste auch negative
        -- Werte enthalten könnte.
\end{code}

\item filter, takeWhile, dropWhile

liefern einen \emph{Teil} der Liste

% FIXME: filter even ...
\begin{code}
filter:: (a->Bool)->[a]->[a]
filter p []      = []
filter p (x:xs)
   |p x          = x: filter p xs
   |otherwise    = filter p xs

> filter even [1..11]
[2,4,6,8,10]

takeWhile:: (a->Bool)->[a]->[a]
takeWhile p []   = []
takeWhile p (x:xs)
   |p x          = x:takeWhile p xs
   |otherwise    = []         -- also Anfangsstück, solange p gilt

dropWhile:: (a->Bool)->[a]->[a]
dropWhile p []   = []
dropWhile p (x:xs)
   |p x          = dropWhile p xs
   |otherwise    = x:xs
\end{code}

\item mehr in Prelude

(einige Definitionen dort aus Gründen der Systematik anders als bei uns,
aber äquivalent)

\item mit solchen HOFs leicht, komplexere Listenverarbeitungsbeispiele
ökonomisch zu formulieren:

z.\,B.:

\begin{code}
> ((foldl (+) 0).(map (^2)).(filter (>0)) [-10..10]
385
\end{code}

also Stufenverarbeitung:

\begin{code}
[-10..10]
     >-------|
             v
          filter (>0)
             |
             |           [1..10]
             v
          map (^2)
             |
             |           [1,4,9,16,25,36,49,64,81,100]
             v
          foldl (+) 0
             |
             >--> 385
\end{code}

\end{itemize}

\section{Wiederaufnahme der Beispiele 3.2 und 3.3}
%FIXME: Referenzen "dynamisch" auf richtigen Abschnitt

Jetzt dasselbe mit HOFs!

\begin{itemize}
\item insertion sort:

\begin{code}
iSort2:: Ord a => [a]->[a]
iSort2 = foldr into []
\end{code}

also:
\texttt{iSort2 [$x_1$\dots$x_n$] = $x_1$ `into` ( $x_2$ `into` (\dots $x_n$ `into` [])\dots)}

\item Datenbank      % FIXME Referenz

\begin{itemize}
\item \emph{replace} ist Kandidat für \emph{map}, weil Elemente der Liste 
verändert werden;

\item \emph{locations} ist Kandidat für:

\begin{itemize}
\item erst \emph{filter} zum Herauslösen der Einträge mit gesuchter Hardware
\item dann \emph{map} für Projektion der verbleibenden Elemente auf 
      Raum-Komponente
\end{itemize}  % FIXME wie schaut das aus??

\item \emph{how\_many}: ähnlich
\end{itemize}

\begin{code}
--------------Alternativformulierung mit higher order functions
---------------------------------------------------------------

is_wanted:: Hardware->(Hardware,Room)->Bool
is_wanted h (h',r) = h == h'

locations2:: Hardware->HwList->[Room]
locations2 h = map snd . filter (is_wanted h)

---------------------------------------------------------------
                                --dasselbe mit operator section

locations3:: Hardware->HwList->[Room]
locations3 h = map snd . filter ((== h).fst)

---------------------------------------------------------------
---------------------------------------------------------------

exchange:: Hardware->Hardware->(Hardware,Room)->(Hardware,Room)
exchange h h' (h'',r)
   |h == h''  = (h',r)
   |otherwise = (h'',r)

replace2:: Hardware->Hardware->HwList->HwList
replac2 h h' = map (exchange h h')
---------------------------------------------------------------

-- how_many: Hausaufgabe!
\end{code}

\end{itemize}


\section{Beispiel: Text-Verarbeitung}
\label{Text-Verarbeitung}

Texte sind zunächst einach \emph{Zeichnreihen}:

\begin{code}
type Text = String
\end{code}

die aber zur Verwaltung / Verarbeitung verschiedenen \emph{Sichtweisen}
unterworfen werden, z.\,B.:

\begin{code}
type Line = String    -- Zeile, ohne '{\bkslash}n'
type Word = String    -- Wort, ohne ' ', '{\bkslash}n'
type Para = [Line]    -- Absatz = Zeilenfolge
\end{code}

Wir betrachten die Umwandlung:

\begin{code}
asLines:: Text->[Line]
\end{code}

zu deren Definition einige Entscheidungen nötig sind (natürlich sind solche
Spezifikationen nicht zwingend):

\begin{enumerate}

\item Text ohne \texttt{'$\backslash$n'} gibt Zeile:

\begin{code}
asLines "Das ist ein Text" = ["Das ist ein Text"]
\end{code}

dann aber auch:

\begin{code}
asLines "" = [""] = [[]]
\end{code}

d.\,h. leerer Text gibt eine Leerzeile.

\item \texttt{'$\backslash$n'} ist \emph{Trennzeichen} 
(nicht: Anfangs-/Endezeichen):

\begin{code}
asLines "Das ist {\bkslash}n ein Text" = ["Das ist", "ein Text"]

asLines "Das ist ein Text{\bkslash}n" = ["Das ist ein Text", []]
\end{code}

d.\,h. \#Zeilen = \#newline + 1

\item Es gibt \emph{keinen} Umbruch gemäß einer maximalen 
Zeilenlänge und \emph{keine} Normalisierung durch Weglassen oder 
Einfügen von Leerzeichen:

\begin{code}
asLines "Das ist    ein Text    " = ["Das ist    ein Text    "]
\end{code}

\end{enumerate}



Lösungsansatz:

wir betrachten versuchsweise die Definition

\begin{code}
asLines = foldr op start
\end{code}

und überlegen uns geeignete Definitionen für \texttt{start} und \texttt{op}.

man erinnere sich:


% FIXME nimmt die gr. Buchstaben bei Referenzen nicht her!!
\begin{enumerate}
\item[$\alpha$] \texttt{foldr :: (a->b->b) -> b -> [a] -> b}
\item[$\beta$]  \texttt{foldr op start [] = start}
\item[$\gamma$] \texttt{foldr op start (x:xs) = x `op` (foldr op start xs)}
\end{enumerate}

wir schließen:

\begin{itemize}
\item \texttt{asLines :: Text->[Line]}, also 
      \texttt{foldr start op :: Text->[Line]}

also wegen $\alpha$:

\begin{code}
b = [Line]
a = Char
\end{code}

also:

\begin{code}
op    :: Char -> [Line] -> [Line]
start :: [Line]
\end{code}

\item \texttt{asLines "" = [[]]} (1.)

andererseits wegen $\beta$:

\begin{code}
asLines "" = foldr op start [] = start
\end{code}

d.\,h.:

\begin{code}
start = [[]]   -- Liste, die nur 1 Leerzeile enthält
\end{code}

\item \texttt{asLines \"{}ein {\bkslash}nText'' = [\"{}ein", \"{}Text"]} (1., 2.)

andererseits wegen $\gamma$:

\begin{code}
asLines "ein {\bkslash}nText"
  = 'e' `op` (asLines "in {\bkslash}nText")
  = 'e' `op` ["in", "Text"]
\end{code}

( wegen 1., 2. )

also:

\begin{code}
op c ls = (c:head ls) : (tail ls)
                      falls c/='{\bkslash}n'
\end{code}

\item 
\texttt{asLines \"{}{\bkslash}n ein {\bkslash}nText" = [[], \"{}ein", \"{}Text"]}
(1., 2.)

andererseits wegen $\gamma$:

\begin{code}
asLines "{\bkslash}n ein {\bkslash}nText"
  = '{\bkslash}n' `op` (asLines "ein {\bkslash}nText")
  = '{\bkslash}n' `op` ["ein", "Text"]
\end{code}

( wegen 1., 2. )

also:

\begin{code}
op c ls = [] : ls          falls c=='{\bkslash}n'
\end{code}

\end{itemize}

also insgesamt:

\begin{code}
asLines:: Text->[Line]
asLines  = foldr break_on_newline [[]]
  where break_on_newline:: Char->[Line]->[Line]
        break_on_newline c ls
          |c == '{\bkslash}n' = []:ls                     --new group
          |otherwise = (c:(head ls)) : (tail ls) --add to group
\end{code}

Die in dieser Definition verwendete Funktion "break\_on\_newline" ist es 
wert, \emph{verallgemeinert} zu werden:

offensichtlich analoge Aufgabe, wenn wir einen \emph{Text} nach \emph{Wörtern} 
gruppieren: dann definiert \texttt{' '} die Bruchstelle,

wenn wir eine Folge von Zeilen nach Absätzen gruppieren: dann definiert
die Leerzeile \texttt{[]} die Bruchstelle.


$\Rightarrow$ aus der Bruchstellenmarkierung einen \emph{Parameter} machen
\emph{und} die Funktion gleich für \emph{beliebige} Listen formulieren.


\begin{code}
------------------------------allgemeines break_on fuer Listen
                          --behandelt break-elem als Separator

break_on:: Eq a => a->a->[[a]]->[[a]]
break_on b c ls
   |c == b    = []:ls                     --new group
   |otherwise = (c:(head ls)) : (tail ls) --add to group

-----------------------------------------------text as lines

asLines:: Text->[Line]
asLines  = foldr (break_on '{\bkslash}n') [[]]
\end{code}

Anwendung z.\,B. so:

\begin{code}
Main> break_on '{\bkslash}n' 'd' [``ef'']
[``def'']
Main> break_on '{\bkslash}n' '{\bkslash}n' [``def'']
[", ``def'']
Main> break_on '{\bkslash}n' '{\bkslash}n' [[]]
[", "]
Main> asLines "
["]
Main> asLines ``abc def''
[``abc def'']
Main> asLines ``{\bkslash}nabc {\bkslash}n{\bkslash}ndef{\bkslash}n''
[", ``abc ``, ", ``def'', "]
\end{code}

jetzt machen wir in \emph{derselben} Weise:
\begin{itemize}
\item aus einer Zeile eine Liste von \emph{Wörtern}: 

Trennzeichen = \texttt{' '}

\item aus einer Liste von Zeilen eine Liste von \emph{Paragraphen} Absätzen:

Trennzeichen = \texttt{[]} = leere Zeile
\end{itemize}

\begin{code}
-----------------------------------------------lines as words
                                             --no empty words

asWords:: Line->[Word]
asWords = filter (/= []) . foldr (break_on ' ') [[]]

-------------------------------------line lists as paragraphs
                                        --no empty paragraphs

asParas:: [Line]->[Para]
asParas = filter (/= []) . foldr (break_on []) [[]]
\end{code}

\begin{wichtig}
Wesentliche Zutat: Wir filtern jetzt \emph{leere Wörter} und leere
\emph{Paragraphen} heraus (sind funktionslos in der angestrebten 
Strukturierung von Texten)
\end{wichtig}

Beispiel (\texttt{microText} ist in einem Skript als der unten gezeigte
String vereinbart):

\begin{code}
Main> microText
"Stille Nacht, {\bkslash}n heilige Nacht, {\bkslash}n{\bkslash}n alles 
schlaeft,{\bkslash}n einsam wacht...{\bkslash}n"
Main> asLines microText
["Stille Nacht, ", " heilige Nacht, ", "", " alles schlaeft,", " einsam wacht...", ""]
Main> asParas (asLines microText)
[["Stille Nacht, ", " heilige Nacht, "], [" alles schlaeft,", " einsam wacht..."]]
Main> map (map asWords) (asParas (asLines microText))
[[["Stille", "Nacht,"], ["heilige", "Nacht,"]], [["alles", "schlaeft,"], 
["einsam", "wacht..."]]]
                     |||-- Liste von Paras
                     ||
                     ||--- Liste von Zeilen
                     |
                     |---- Liste von Worten
\end{code}

Unsere drei Funktionen lassen sich jtzt zusammensetzen, um die \emph{Struktur}
eines Texts zu analysieren (to parse = zerteilen):

\begin{code}
parse:: Text->[[[Word]]]
parse = map(map asWords) . asParas . asLines
\end{code}

also z.\,B.:

\begin{code}
Main> microText
"Stille Nacht, {\bkslash}n heilige Nacht, {\bkslash}n{\bkslash}n alles schlaeft,{\bkslash}n einsam wacht...{\bkslash}n"
Main> parse microText
[[["Stille", "Nacht,"], ["heilige", "Nacht,"]], [["alles", "schlaeft,"], 
["einsam", "wacht..."]]]
\end{code}

also:

\texttt{
\begin{tabular}{r@{ ::= }l}
<Text> & [<Para>]\\
<Para> & [<Line>]\\
<Line> & [<Word>]\\
<Word> & <print\_char> \{<print\_char>\}\\
\end{tabular}
}

(diese syntaktischen Variablen sind natürlich nicht identisch mit den 
Haskell Typen)


jetzt neue Aufgabe:

mache Strukturanalyse wieder \emph{rückgängig} (d.\,h. mache das Resultat
von parse wieder "`flach"')

dazu: füge alle nötigen \emph{Separatoren} wieder ein!

Dieses Einfügen formulieren wir gleich allgemein, für beliebige Listen 
$\Rightarrow$ \texttt{concWith}

und wenden diese Operation an mit \texttt{foldr1} (=kein Startelement!)

\begin{code}
-------------------------------allgemeines concWith fuer Listen

concWith:: a->[a]->[a]->[a]
concWith x ys zs = ys ++ [x] ++ zs

-----------------------------------------------Umkehrfunktionen
                                        --re-insert Separatoren

unLines:: [Line]->Text
unLines = foldr1 (concWith '{\bkslash}n')

unWords:: [Word]->Line
unWords = foldr1 (concWith ' ')

unParas:: [Para]->[Line]
unParas = foldr1 (concWith [])
\end{code}

\begin{wichtig}
beachte:
\begin{itemize}
\item \emph{keine} exakten \emph{Umkehrfunktionen}, da wir überflüssige 
Separatoren entfernt haben;
\item funktioniert wegen foldr1 \emph{nicht} für \emph{leere} Listen!
\end{itemize}
\end{wichtig}

\begin{code}
Main> (unLines.asLines) "abc {\bkslash}ndef{\bkslash}n"
"abc {\bkslash}ndef{\bkslash}n"
Main> (asLines.unLines)["abc ", "def", ""]
["abc ", "def", ""]
Main> (unWords.asWords) "abc  def "
"abc def"
Main> (asWords.unWords) ["abc", "def"]
["abc", "def"]
Main> (unWords.asWords) ""
"
Program error: {foldr1 (concWith ' ') []}


Main> (unWords.asWords) " "
"
Program error: {foldr1 (concWith ' ') []}
\end{code}

damit dann die gewünschte Umkehrung von parse:

\begin{code}
unparse:: [[[Word]]]->Text
unparse = unLines . unParas . map(map unWords)
\end{code}

Beispiel:

\begin{code}
Main> (unparse.parse) microText
"Stille Nacht,{\bkslash}nheilige Nacht,{\bkslash}n{\bkslash}nalles schlaeft,{\bkslash}neinsam wacht..."

             = vereinfachte (nicht redundante) Form des Ausgangstexts
\end{code}

\begin{code}
simplify:: Text->Text        --entferne redundante Separatoren
simplify = unparse . parse
\end{code}

Beispiel:

\begin{code}
Main> simplify microText
"Stille Nacht,{\bkslash}nheilige Nacht,{\bkslash}n{\bkslash}nalles schlaeft,{\bkslash}neinsam wacht..."
Main> putStr (simplify microText)
Stille Nacht,
heilige Nacht,

alles schlaeft,
einsam wacht...
\end{code}


Analyse der Struktur eines Texts durch parse kann als Ausgangspunkt dienen
für viele weitere nützliche Arbeiten, z.\,B.:

\begin{itemize}
\item Eigenschaften eines Texts ermitteln,
\item Änderungen des Texts vornehmen,
\item Druckbild gestalten, \dots
\end{itemize}


Beispiel: Texteigenschaften:

\begin{code}
countLines = length . asLines
countWords = length . concat. map asWords . asLines
countParas = length . asParas . asLines


Main> countLines microText
6
Main> countWords microText
8
Main> countParas microText
2
\end{code}


Beispiel: Layout

wir betrachten einige einfache Möglichkeiten, aus einem Text ein 
gewünschtes \emph{Druckbild} zu erzeugen;

dabei \emph{Einschränkungen}:

\begin{itemize}
\item benutze \emph{Zeilenstruktur}, die der Hersteller des Texts vorgegeben
hat (also kein Zeilenumbruch, aber auch kein Umbruch größerer Einheiten 
wie  z.\,B. Seiten)

\item und normiere Zeilen lediglich durch Einfügen von Füllmaterial
(oder Abschneiden) am \emph{rechten} Rand!
\end{itemize}

unser \emph{Layout} arbeitet mit \emph{Textblöcken} = Folgen von Zeilen
gleicher Länge

und arrangiert diese durch vertikale und horizontale \emph{Komposition},
z.\,B.:

\vspace{1em}
\setlength{\unitlength}{0.5cm}
\begin{picture}(4,4)
\put(0,0){\framebox(4,0.9){}}
\put(0,1.1){\framebox(1.9, 2.9){}}
\put(2.1,1.1){\framebox(1.9, 2.9){}}
\end{picture}
\vspace{1em}

Textblöcke sind bei uns einfach Listen von Zeichen, und die fällige
Normierung der Länge (Einfügen / Abschneiden rechts) formulieren wir gleich 
in voller Allgemeinheit für beliebige Listen (weil wir damit dann auch 
die Höhe von Textblöcken normieren können):

\begin{code}
--Textblock = Char-Rechteck, d.h. Folge von gleichlangen Zeilen

type Block = [Line]                              --type synonym

------------------------------------------------Hilfsfunktionen

copy:: Int->a->[a]                --Liste mit n-mal elem
copy (n+1) elem = elem : copy n elem
copy _ _ = []

ljustify:: Int->a->[a]->[a]    --normiert Liste auf Laenge n
                               --rechts Abschneiden/Auffuellen
ljustify n filler list
      = take n list ++ copy (n - (length list)) filler
\end{code}

Beispiel:

\begin{code}
Main> copy 9 'a'
"aaaaaaaaa"
Main> copy 9 "a"
["a", "a", "a", "a", "a", "a", "a", "a", "a"]
Main> copy (-2) "a"
[]
Main> ljustify 10 '*' "abc"
"abc*******"
Main> ljustify 10 0 [1,2,3,4,5]
[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
Main> ljustify 0 ' ' "abc"
""
\end{code}

Ein \emph{Textblock} entsteht durch Normierung von \emph{Zeilenlänge}
(=Breite des Blocks) und \emph{Zeilenanzahl} (=Höhe des Blocks)

\begin{code}
----------------------------line lists as height*width blocks

asBlock:: Int->Int->[Line]->Block
asBlock height width
       = ljustify height (copy width ' ')           --Hoehe
               . map (ljustify width ' ')           --Breite
\end{code}

Beispiel:

\begin{code}
Main> asBlock 3 10 ["erste Zeile", "zweite Zeile"]
["erste Zeil", "zweite Zei", "          "]
Main> asBlock 3 15 ["erste Zeile", "zweite Zeile"]
["erste Zeile    ", "zweite Zeile   ", "               "]
Main> putStr (unLines (asBlock 3 15 ["erste Zeile", "zweite Zeile"]))
erste Zeile
zweite Zeile

Main> putStr (unLines (asBlock 2 10 ["Zeile", "Zeile", "keine Zeile"]))
Zeile
Zeile
Main> ((asBlock 5 30).asLines.simplify) microText
["Stille Nacht,                 ", "heilige Nacht,                ", "
                    ", "alles schlaeft,               ", "einsam wacht...
        "]
Main> (putStr.unLines.(asBlock 5 30).asLines.simplify) microText
Stille Nacht,
heilige Nacht,

alles schlaeft,
einsam wacht...
\end{code}

Textblöcke (geeigneter Dimension) lassen sich \emph{horizontal} und
\emph{vertikal} kombinieren:

\begin{code}
----------------------------------Komposition von Textbloecken

combHori, combVerti:: Block->Block->Block

combHori = zipWith (++)          --requires equal heights!!!
combVerti = (++)                 --requires equal widths!!!
\end{code}

Dabei ist zipWith eine higher-order Standardfunktion:

\begin{code}
zipWith :: (a->b->c)->[a]->[b]->[c]

zipWith op (x:xs) (y:ys) = x `op` y : zipWith op xs ys
zipWith _ _ _            = []      -- eine Liste erschöpft
\end{code}


%FIXME: Reißverschlußbild

Es folgt ein Layout-Beispiel für

\begin{code}
microText = "Stille Nacht ..."     -- wie gehabt
\end{code}

und

\begin{code}
headline = "Weihnachten in Salzburg"
\end{code}


Layout-Beispiel:

\begin{code}
layout1 =
  (putStr.unLines)
    (combVerti
       (asBlock 1 30 [])
       (combVerti
          (((asBlock 2 30).asLines.simplify) headline)
          (((asBlock 6 30).asLines.simplify) microText)))


layout2 =
  (putStr.unLines)
   (combVerti
    (asBlock 1 34 [])
    (combVerti
     (((asBlock 2 34).asLines.simplify) headline)
     (combHori
      (((asBlock 3 17).asLines.simplify) microText)
      (((asBlock 3 17).(drop 3).asLines.simplify) microText))))



Hugs session for:
/usr/local/lib/hugs/lib/Prelude.hs
text_proc
Main> layout1

Weihnachten in Salzburg

Stille Nacht,
heilige Nacht,

alles schlaeft,
einsam wacht...

Main> layout2

Weihnachten in Salzburg

Stille Nacht,    alles schlaeft,
heilige Nacht,   einsam wacht...
\end{code}

\setlength{\parindent}{0em}

\section{Effizienz}

Die oft große \emph{Ökonomie} in der \emph{Formulierung} einer Lösung
darf nicht darüber hinwegtäuschen, daß es erhebliche \emph{Kosten}
(\emph{Laufzeit}, \emph{Speicherplatz}) bei der \emph{Ausführung}
geben kann;\\

deshalb immer nötig:

\begin{itemize}
\item Anwendung allgemeiner Strategien (z.\,B. divide \& conquer)
\item Verständnis des Ausführungs- (Reduktions-) Prozesses
\item Modellierung/Tests zur Lokalisierung von Problemen
\end{itemize}
\emph{Beispiel:}

die Funktion \emph{"`aslines"'} in \ref{Text-Verarbeitung} wurde mit
\emph{foldr} definiert, kann aber in analoger Weise auch mit
\emph{foldl} abgestützt werden!\\

Unterschiede bei Definition:

Anhängen \emph{von rechts} (ans Ende) des jeweils bereits gewonnen
Teilergebnisses.

\begin{code}
------------------------asLines: realisiert mit foldr und foldl

copy:: Int->a->[a]                --Liste mit n-mal elem                    
copy (n+1) elem = elem : copy n elem
copy _ _ = []

break1:: Char->[[Char]]->[[Char]]
break1 c ls
   |c == '{\bkslash}n' = [[]] ++ ls                     --new group
   |otherwise = [[c]++(head ls)] ++ (tail ls)  --add to group

asLines1:: [Char]->[[Char]]
asLines1  = foldr break1 [[]]


break2:: [[Char]]->Char->[[Char]]
break2 ls c
   |c == '{\bkslash}n' = ls ++ [[]]                     --new group
   |otherwise = (init ls) ++ [(last ls)++[c]]  --add to group

asLines2:: [Char]->[[Char]]
asLines2  = foldl break2 [[]]

\{-----------------------------Beispielanwendungen asLines1/2:

Main> length (asLines1 (copy 1000 'a')) 
1
(15023 reductions, 32026 cells)
Main> length (asLines2 (copy 1000 'a'))
1
(14023 reductions, 30026 cells, 1 garbage collection)

Main> length (asLines1 (copy 1000 '{\bkslash}n'))
1001
(19024 reductions, 32033 cells)
Main> length (asLines2 (copy 1000 '{\bkslash}n'))
1001
(518524 reductions, 1531533 cells, 17 garbage collections)

-----------------------------------------------------------\}
\end{code}

\begin{tabularx}{\linewidth}{lX}
  \emph{also:} & im Falle von '$\backslash$n' = Beginn neuer Zeile
  \emph{gewaltige} Verschlechterung bei \emph{foldl}-Version!
\end{tabularx}\\

genauere Analyse \emph{sehr mühsam},\\

\emph{hier nur:}
\begin{itemize}
\item Laufzeit (Reduktionen)
\item einfacheres (aber ähnliches) Beispiel.
\end{itemize}

zur \emph{Erinnerung}:

foldr $\otimes$ a [$x_1$,\ldots,$x_n$]\\
$\Rightarrow$ $x_1$ $\otimes$ (foldr $\otimes$ a [$x_2$,\ldots,$x_n$]\\
$\vdots$\\
$\Rightarrow$ $x_1$ $\otimes$ ($x_2$ $\otimes$ (\ldots($x_n$
$\otimes$ a)\ldots))\\

foldl $\otimes$ a [$x_1$,\ldots,$x_n$]\\
$\Rightarrow$ foldl $\otimes$ (a $\otimes$ $x_1$) [$x_2$,\ldots,$x_n$]\\
$\vdots$\\
$\Rightarrow$ (\ldots((a $\otimes$ $x_1$)$\otimes$ 
$x_2$)$\otimes$ \ldots)\ldots)$\otimes$ $x_n$\\

\emph{dann:} wichtig, ob Operator $\otimes$ strikt ist oder nicht!

\emph{Beispiele:}\\
\begin{tabularx}{\linewidth}{lX}
  Addition (+) & = strikt\\
  log. Und (\&\&) & = nicht strikt in 2.Argument, falls 1.Argument
  False: False \&\& ? == False
\end{tabularx}

\begin{code}
-------------------------------------------fold with strict op
Main> foldr (+) 0 [1..1000]
500500
(\emph{13020} reductions, 17032 cells)
Main> foldl (+) 0 [1..1000]
500500
(\emph{13020} reductions, 18032 cells)

----------------------------------------fold with non-strict op

Main> foldr (&&) True [\emph{False},True,True,True,True,True,True,True,True,True]
False
(\emph{15} reductions, 31 cells)
Main> foldr (&&) True [True,True,True,True,True,\emph{False},True,True,True,True]
False
(\emph{25} reductions, 41 cells)
Main> foldr (&&) True [True,True,True,True,True,True,True,True,True,\emph{False}]
False
(\emph{33} reductions, 49 cells)

Main> foldl (&&) True [\emph{False},True,True,True,True,True,True,True,True,True]
False
(\emph{34} reductions, 59 cells)
Main> foldl (&&) True [True,True,True,True,True,\emph{False},True,True,True,True]
False
(\emph{34} reductions, 59 cells)
Main> foldl (&&) True [True,True,True,True,True,True,True,True,True,\emph{False}]
False
(\emph{34} reductions, 59 cells)

--------------------------------------------------------------
\end{code}

\emph{Analyse:}\\

\emph{Fall (+):} $\approx$ \emph{gleiche} Effizienz!\\

\emph{foldr} (+) 0 [1,\ldots,1000]\\
\ldots $\Rightarrow$ 1+(2+ \ldots +(1000+0)\ldots)\\

\emph{foldl} (+) 0 [1,\ldots,1000]\\
\ldots $\Rightarrow$ (\ldots((0+1)+2)\ldots)+1000\\

in \emph{beiden} Fällen Aufbau des \emph{ganzen} Ausdrucks, bevor
erste Addition \ldots\\

(! lazy evaluation: Bei foldl werden die Teilsummen unausgewertet
mitgeschleppt; es gibt eine Variante von foldl, die das nicht macht
und in manchen Situationen besser ist)

\emph{Fall (\&\&):} \emph{unterschiedliche} Effizienz!\\

\emph{foldr} (\&\&) True [True, \ldots, False, \ldots, True]\\
\ldots $\Rightarrow$ True \&\& (\ldots (False \&\& (foldr (\&\&) True [True,
\ldots, True])\ldots)

\begin{tabularx}{\linewidth}{lX}
  aber:   & False \&\& "`irgendwas"' = False\\
  d.\,h.: & \emph{fertig} sobald False angetroffen
\end{tabularx}\\

\emph{foldl} (\&\&) True [True, \ldots, False, \ldots, True]\\
\ldots $\Rightarrow$ (\ldots (\ldots (True \&\& True) \&\& \ldots) \&\&
False) \&\& \ldots)\\
d.\,h.: erst ganzen Ausdruck aufbauen

\begin{code}
------------------------------------------------Konkatenation
concTwo:: Int->Int
concTwo m = length ((copy m 'a') ++ "0123456789")

\{------------------------------------------------Anwendungen:

Main> concTwo 1
11
(84 reductions, 121 cells)
Main> concTwo 10
20
(219 reductions, 346 cells)
Main> concTwo 100
110
(1569 reductions, 2597 cells)
Main> concTwo 1000
1010
(15069 reductions, 25098 cells, 1 garbage collection)
Main> concTwo 10000
10010
(150069 reductions, 250099 cells, 2 garbage collections)

------------------------------------------------------------\}
\end{code}

Zahlen lassen vermuten, daß Aufwand für (++) \emph{linear} abhängt von
\emph{Länge} des \emph{linken} Arguments;\\
in der Tat:

\begin{math}
  \left.
    \begin{array}{l} 
      [] ++ ys = ys\\
      (x:xs)++ys = x:(xs++ys)
    \end{array}
  \right\} Def.\ (++)
\end{math}\\

d.\,h.\\
\begin{tabularx}{\linewidth}{lX}
(++) & braucht \emph{linkes} (\emph{nicht} rechtes) Argument und
durchläuft dies \emph{elementweise}, also Aufwand bestimmt durch
\emph{Länge} des \emph{linken} Arguments!
\end{tabularx}\\

\emph{jetzt:} \emph{fold} zusammen mit \emph{(++)}:

\begin{code}
---------------------------einfacheres foldr/foldl (++) Beispiel

right, left:: Int->Int
right m = length (foldr (++) [] (copy m "0123456789"))
left m  = length (foldl (++) [] (copy m "0123456789"))

\{--------------------------------------Beispielanwendungen

Main> right \emph{1}
10
(\emph{90} reductions, 145 cells)
Main> right \emph{10}
100
(\emph{729} reductions, 1118 cells)
Main> right \emph{100}
1000
(\emph{7119} reductions, 10839 cells)
Main> right \emph{1000}
10000
(\emph{71019} reductions, 108040 cells, 2 garbage collections)

Main> left \emph{1}
10
(\emph{80} reductions, 116 cells)
Main> left \emph{10}
100
(\emph{1079} reductions, 2178 cells)
Main> left \emph{100}
1000
(\emph{55619} reductions, 156439 cells, 1 garbage collection)
Main> left \emph{1000}
10000
(\emph{5056019} reductions, 15064040 cells, 163 garbage collections)

-------------------------------------------------------------\}
\end{code}

\begin{tabularx}{\linewidth}{lcX}
  Vermutung: & right & \emph{linear}\\
             & left  & \emph{quadratisch}
\end{tabularx}\\

\emph{Analyse:}\\
(grob, unter Vernachlässigung von copy)\\

sei $l_1 = l_2 = \ldots = l_m = "`0123456789"'$\\

dann:\\
\emph{foldr} (++) [] [$l_1$, \ldots, $l_m$]\\
$\Rightarrow$ $l_1$ ++ (foldr (++) [] [$l_2$, \ldots, $l_m$])\\
$\vdots$\\
$\Rightarrow$ '0': ('1': \ldots ('9': (foldr (++) [] [$l_2$, \ldots,
$l_m$])\ldots)\\
$\Rightarrow$ usw.

\begin{tabularx}{\linewidth}{lX}
  \emph{also} & (++) wird \emph{n-mal} angewendet auf ein linkes
  Argument der \emph{Konstanten} Länge 10, d.\,h. Schrittzahl
  $\stackrel{\wedge}{=}$ \emph{O(n)}
\end{tabularx}\\

\emph{foldl} (++) [] [$l_1$, \ldots, $l_m$]\\
$\Rightarrow$ foldl (++) ([] ++ $l_1$) [$l_2$, \ldots, $l_m$]\\
$\Rightarrow$ foldl (++) (([] ++ $l_1$) ++ $l_2$) [$l_3$, \ldots,
$l_m$]\\
$\vdots$\\
$\Rightarrow$ (\ldots (([] ++ $l_1$) ++ $l_2$) ++ \ldots ) ++ $l_m$

\begin{tabularx}{\linewidth}{lX}
\emph{also} & (++) wird \emph{n-mal} angewendet auf ein linkes
Argument der \emph{wachsenden} Länge 0, 10, 20, \ldots, (m-1)*10,
d.\,h. Schrittzahl $\stackrel{\wedge}{=}$ O($m^2$)
\end{tabularx}

\section{Unendliche Listen}

\begin{itemize}
\item entstehen aus \emph{nicht-terminierenden} Berechnungen (die
  Listen erzeugen),

\item sind nützliches Zwischenergebnis zur \emph{Komposition} von
  Teilberechnungen,

\item sind \emph{praktikabel} wegen {lazy evaluation}: unendliche
  Liste wird \emph{nicht} komplett erzeugt, sondern nur soweit
  \emph{Bedarf} besteht (es ist nützlich, sich \emph{vorzustellen},
  eine solche Liste sei tatsächlich vorhanden -- vgl. Mathematik:
  z.\,B. \{x $<$ 100 $|$ x $\in$ $N$\} obwohl man immer nur \emph{endliche}
  Anfangsstücke braucht!)
\end{itemize}

\emph{Beispiel:} Wiederholung ohne Ende:

\begin{code}
iterate :: (a->a)->a->[a]
iterate f x = x : (iterate f (f x))
\end{code}

also: [x, f x, f(f x), \ldots]

\begin{code}
Main> iterate (+2) 1
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, ...
1537, 1539, 1541, 1543, 1545, 1547, 1549, {Interrupted!}     --Control C
Main> take 5 (iterate (+2) 1)
[1, 3, 5, 7, 9]
(120 reductions, 209 cells)
Main> take 1 (drop 99 (iterate (+2) 1))
[199]
(1324 reductions, 1933 cells)
Main> take 10 [1..]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
(239 reductions, 437 cells)
Main> take 10 [1,3..]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
(224 reductions, 415 cells)
\end{code}

dabei \emph{Kurzformen} wie:\\
\begin{tabularx}{\linewidth}{lX}
  \ [1..]   & für iterate (+1) 1\\
  \ [1,3..] & für iterate (+2) 1
\end{tabularx}\\

\emph{Analyse:}\\
take 2 (iterate (+2) 1)\\
$\Rightarrow$ take 2 (1 : iterate (+2) (1+2))\\
$\Rightarrow$ 1 : (take 1 (iterate (+2) (1+2)))\\
$\Rightarrow$ 1 : (take 1 (iterate (+2) 3))\\
$\Rightarrow$ 1 : (take 1 (3 : (iterate (+2) (3+2)))\\
$\Rightarrow$ 1 : 3 : (take 0 (iterate (+2) (3+2)))\\
$\Rightarrow$ 1 : 3 : []

\section{Beispiel: Erzeugung von Primzahlen}

Eratosthenes erfand die \emph{Siebmethode}:\\
\hspace*{1em}starte mit L=[2,3,4,5,\ldots]\\
\hspace*{1em}loop\\
\hspace*{2em}entferne alle Vielfachen von head L aus L\\
\hspace*{1em}end loop\\

wobei man als \emph{Invariante} hat:\\
head L ist Primzahl, da von keiner kleineren Primzahl geteilt!\\
Also muß man unterwegs bloß alle head L ausgeben!

Die Schleife für das wiederholte Sieben läßt sich durch iterate
realisieren, für das Sieben selbst definieren wir eine Funktion
"`crossout"', die eine geeignete Anwendung von "`filter"' ist:

\begin{code}
--------------------------------------------------prime numbers

crossout::[Int]->[Int]         --elim multiples of head element
crossout (x:xs) = filter ({\bkslash}y->y`rem`x /= 0) xs

primeNumbers :: [Int]
primeNumbers = map head (iterate crossout [2..])

\{-
Main> take 10 (crossout [2..])
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
Main> take 10 primeNumbers
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Main> take 1 (drop 9 primeNumbers)  -- 10. Primzahl
[29]
Main> primeNumbers !! 9   --Indexierung mit (!!) beginnt mit 0
29
Main> primeNumbers !! 99
541
Main> primeNumbers !! 999


ERROR: Garbage collection fails to reclaim sufficient space
-\}
\end{code}

 
\begin{tabularx}{\linewidth}{lX}
\emph{Erklärung:} & iterate crossout [2..] liefert \emph{unendliche
  Liste} von \emph{unendlichen Listen:}\\
\end{tabularx}

%latex2html kann mit meinen schönen Tabellen leider nicht umgehen
\begin{latexonly}
\begin{tabular}{lrcccccl}
 & [[ & 2, & 3, &  4, &  5, & \ldots & ],\\
 &  [ & 3, & 5, &  7, &  9, & \ldots & ],\\
 &  [ & 5, & 7, & 11, & 13, & \ldots & ],\\
 &&\raisebox{-1.5ex}[1.5ex]{$\vdots$}& & & & &\\
 &    &    &    &     &     &        & ] \\
\end{tabular}\\
\end{latexonly}

\begin{rawhtml}
<pre><br>
[ [  2  3  4   5  ... ],<br>
  [  3  5  7   9  ... ],<br>
  [  5  7 11  13  ... ],<br>
   ... <br>
                       ]<br>
</pre>
\end{rawhtml}

die Primzahlen selbst kriegt man durch map head:

\begin{latexonly}
\begin{tabular}{lr|c|ccccl} \cline{3-3}
 & [[ & 2, & 3, &  4, &  5, & \ldots & ],\\
 &  [ & 3, & 5, &  7, &  9, & \ldots & ],\\
 &  [ & 5, & 7, & 11, & 13, & \ldots & ],\\
 &&\raisebox{-1.5ex}[1.5ex]{$\vdots$}& & & & &\\
 &    &    &    &     &     &        & ] \\ \cline{3-3}
\end{tabular}
\end{latexonly}

\begin{rawhtml}
<pre><br>
    +-+<br>
[ [ |<b>2</b>| 3  4   5  ... ],<br>
  [ |<b>3</b>| 5  7   9  ... ],<br>
  [ |<b>5</b>| 7 11  13  ... ],<br>
   ... <br>
    +-+                ]<br>
</pre>
\end{rawhtml}

\section{Beispiel: Numerische Differentation und Integration}

Wir betrachten zunächst nochmal numerische Differentation:\\

die mathematische Definition
\[ f'(x) = \lim_{h\to 0} \frac{f(x+h)-f(x)}{h} \]
führt für beliebige feste Wahl der Intervallbreite h auf

\begin{code}
simpleDiff:: (Double->Double)->Double->Double->Double
simpleDiff f x h = (f(x+h)-f(x))/h
\end{code}

Wir erzeugen jetzt eine \emph{Folge} von Näherungswerten, indem wir
simpleDiff auf eine \emph{Folge} von \emph{abnehmenden
  Intervallbreiten} anwenden:\\

\begin{tabularx}{\linewidth}{lX}
iterate (/2) & liefert Folge von Intervallbreiten durch fortgesetzte
Halbierung
\end{tabularx}\\

damit dann:
\begin{code}
seqDiff:: (Double->Double)->Double->Double->[Double]
seqDiff f x = map (simpleDiff f x) . iterate (/2)
\end{code}

also:

\setlength{\unitlength}{0.5cm}
\begin{picture}(15,17)
\makebox[0cm][l]{ %ohne diese zusätzliche Box funktioniert latex2html nicht!
\put(6,16){h}
\put(6.5,16.25){\line(1,0){0.5}}
\put(7,16.25){\vector(0,-1){1.25}}
\put(7,14){\oval(5,2)\makebox(0,0){iterate (/2)}}
\put(7,13){\vector(0, -1){2}}
\put(8,12){[h, h/2, h/4, \ldots]}
\put(7,10){\oval(8,2)\makebox(0,0){map(simpleDiff f x)}}
\put(7,9){\vector(0,-1){3}}
\put(8,7.5){$[ \frac{f(x+h)-fx}{h}, \frac{f(x+
    \frac{h}{2})-fx}{\frac{h}{2}}, \ldots ]$}
\put(10,4){\oval(15,4)\makebox(0,0){\parbox[c]{6cm}{darauf dann eine Funktion
    anwenden, die eine genügend gute Approximation auswählt}}}
\put(7,2){\line(0,-1){1}}
\put(7,1){\vector(1,0){0.75}}
\put(8,0.75){Ergebnis}
}
\end{picture}

$\Rightarrow$ vgl. Seite \pageref{withinEpsSrc}\\

\emph{jetzt Problem:}\\
läßt sich die "`Konvergenzgeschwindigkeit"' verbessern?\\

\emph{plausibel:}\\
\emph{Fehler} eines Näherungswertes \emph{hängt ab} von
\emph{Intervallbreite} h, also im einfachsten Fall \emph{lineare}
Abhängigkeit:\\
$A_n$ = W + K*h\\
wobei:\\
$A_n$ = n-te Approximation\\
W = wahrer Wert\\
K = Koeffizient\\

also:\\
$A_n$ = W + K*h\\
$A_{n+1}$ = W + K*h/2\\
$\Rightarrow$ W = 2*$A_{n+1}$ - $A_n$\\

so definierte W-Werte sind natürlich auch noch ein bißchen falsch,
d.\,h. Näherung\\
$\Rightarrow$ mache daraus wieder eine Folge!\\

seqDiff: 
\begin{tabular}{llccccccr}
\ & [ & $A_1$ & & $A_2$, & & $A_3$, & \ldots & ]\\
\ &   & $\downarrow$ & $\swarrow$ & $\downarrow$ & $\swarrow$ & & & \\
\ & [ & $W_1$ & & $W_2$, & &        & \ldots & ]\\
\end{tabular}\\

diese zweite Folge wird erzeugt durch:
\begin{code}
betterSeqDiff:: (Double->Double)->Double->Double->[Double]
betterSeqDiff f x = elimFstOrdError . seqDiff f x
\end{code}

\emph{wobei:}
\begin{code}
elimFstOrdError:: [Double]->[Double]
elimFstOrdError (x1:x2:xs)       --assumes halving of distances
     = (2*x2-x1):(elimFstOrdError (x2:xs))
--      -------unsere Formel
\end{code}

$\Rightarrow$ Seite \pageref{elimFstOrdErrorSrc}

\begin{code}
--------------------------------------infinite lists: examples

------------------------------------------------------numerics
-------------------------------------------auxiliary functions

\label{withinEpsSrc}
withinEps:: Double->[Double]->Double    
withinEps eps (x1:x2:xs)
   |abs(x1 - x2) <= eps = x2
   |otherwise           = withinEps eps (x2:xs)

\label{elimFstOrdErrorSrc}
elimFstOrdError:: [Double]->[Double]                                            
elimFstOrdError (x1:x2:xs)       --assumes halving of distances
     = (2*x2-x1):(elimFstOrdError (x2:xs))


-------------------------------------------------differentiation
simpleDiff:: (Double->Double)->Double->Double->Double
simpleDiff f x h = (f(x+h)-f(x))/h

seqDiff:: (Double->Double)->Double->Double->[Double]
seqDiff f x = map (simpleDiff f x) . iterate (/2)

betterSeqDiff:: (Double->Double)->Double->Double->[Double]
betterSeqDiff f x = elimFstOrdError . seqDiff f x

\{-
Main> take 5 (seqDiff cos 0 0.1)
[-0.0499582, -0.0249946, -0.0125003, -0.00625134, -0.00312805]
Main> take 5 (betterSeqDiff cos 0 0.1)
[-3.09944e-05, -5.96046e-06, -2.38419e-06, -4.76837e-06, 0.0]
Main> withinEps 0.001 (seqDiff cos 0 0.1)
-0.000762939
Main> withinEps 0.001 (betterSeqDiff cos 0 0.1)
-5.96046e-06
-\}
-----------------------------------------------------integration
simpleIntegrate:: (Double->Double)->Double->Double->Double
simpleIntegrate f a b = (f a + f b) * (b-a)/2

seqIntegrate:: (Double->Double)->Double->Double->[Double]
seqIntegrate f a b = (simpleIntegrate f a b) 
                      : (zipWith (+) (seqIntegrate f a m)
                                     (seqIntegrate f m b))
                      where m = (a+b)/2
                      --inefficient: recomputations of fa,fb,fm


\{-
Main> take 10 (seqIntegrate sin 0 pi)
[-1.37323e-07, 1.5708, 1.89612, 1.97423, 1.99357, 1.99839, 1.9996, 1.9999, 1.99997, 1.99999]
Main> withinEps 0.001 (seqIntegrate sin 0 pi)
1.9999
-\}
\end{code}

mit der \emph{Integration} verfahren wir ähnlich:\\

ein grobes Verfahren ist offenbar:\\

\begin{code}
simpleIntegrate:: (Double->Double)->Double->Double->Double
simpleIntegrate f a b = (f a + f b) * (b-a)/2
\end{code}

Wir gewinnen eine \emph{Folge} von \emph{Approximationswerten}, indem
wir (wiederholt)
\begin{itemize}
\item das \emph{Intervall} [a,b] \emph{halbieren}
\item die \emph{Ergebnisse} für beide Hälften \emph{addieren}
\end{itemize}

\begin{code}
seqIntegrate:: (Double->Double)->Double->Double->[Double]
seqIntegrate f a b = (simpleIntegrate f a b) 
                      : (zipWith (+) (seqIntegrate f a m)
                                     (seqIntegrate f m b))
                      where m = (a+b)/2
                      --inefficient: recomputations of fa,fb,fm
\end{code}

\begin{wichtig}
beachte: Ergebnis wieder \emph{Folge} von Näherungswerten, aber
\emph{komplexere Struktur} der Rekursion: Baum, (Kaskade)
\end{wichtig}


\section{Beispiel: Modellierung von Schaltungen}

Wir basteln uns ein \emph{Flipflop!}

%FIXME: Bildchen.


\begin{tabular}{lcl}
\emph{Zustand} des Flipflops & $\widehat{=}$ & 
Belegung von q, q' ( q= $\neg$ q') \\

Zustand \emph{unverändert}   & $\widehat{=}$ & (set, reset) = (1, 1) \\

\emph{Veränderung}           & $\widehat{=}$ & set = 0  $\Rightarrow$  q = 0 \\
                             & & reset = 0  $\Rightarrow$  q' = 0 \\
\end{tabular}

\textbf{Modellierung:}

\begin{itemize}
\item \begin{tabularx}{\linewidth}{l@{ $\widehat{=}$ }X}
set, reset, q, q' & unendliche Listen von Werten, wobei jede Position in Liste
einem Zeit-Takt entspricht\\
\end{tabularx}

\item \emph{Verzögerung} (3 Zeiteinheiten) damit Rückkopplung möglich

\item Sonderfall: \emph{undefinierter} Wert
\end{itemize}

\begin{code}
------------------------------------------------ flip-flop model

data ThreeVal = U | L | H          -- undefined, low, high
     deriving Show

nand :: ThreeVal->ThreeVal->ThreeVal
nand H H = L
nand L _ = H
nand _ L = H
nand _ _ = U

nandSeq :: [ThreeVal]->[ThreeVal]->[ThreeVal]
nandSeq = zipWith nand


q, q', set, reset :: [ThreeVal]

q  = U : U : U : nandSeq set q'
q' = U : U : U : nandSeq reset q

set   = [L,L,L,L,L,L,L,H,H,H,H,H,H,H,H,H,H,H,H,H,H,H,H,H,H,H]
reset = [H,H,H,H,H,H,H,H,H,H,H,H,H,H,L,L,L,L,L,L,L,H,H,H,H,H]

\{-
Main> q
[U, U, U, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, L, 
L, L, L, L, L, L, L, L]
Main> q'
[U, U, U, U, U, U, L, L, L, L, L, L, L, L, L, L, L, H, H, H, H, 
H, H, H, H, H, H, H, H]
-\}
\end{code}


\chapter{Benutzerdefinierte Datentypen und Typklassen}

\section{Algebraische Datentypen}

= "`konkrete"' Datentypen,

Konstruktion der Elemente des Types liegt offen und ist Basis für
\begin{itemize}
\item Benennung einzelner Elemente
\item Definition von Funktionen über dem Typ
\end{itemize}


Beispiel: $\Rightarrow$ Seite \pageref{algebraic_type_bsp}

Beachte:

\begin{itemize}
\item linke Seite: Schlüsselwort ``data'', dann Typname

\item rechte Seite: \emph{Konstruktionsschema} für Elemente des Typs,
unter Verwendung von:

\begin{itemize}
\item Alternativsymbol ``$|$''
\item andere Typen
\item Konstruktoren, d.\,h. 0,1,2 \dots stellige Funktionen
\end{itemize}

\item Interpretation: zum Typ gehört alles, was sich aus wiederholter
Anwendung des Konstruktionschemas erzeugen läßt, vgl. Mathematik:

\[ 0 \in N \]
\[ n \in N \Rightarrow succ(n) \in N  \]

in Haskell-Stil:
\begin{code}
data N = Zero | Succ N
\end{code}

\end{itemize}


\begin{code}
\label{algebraic_type_bsp}
----------------------------------------- algebraic data types
---------------------------------------------- simple examples

data PrimaryColour = Yellow | Red | Blue   -- enumeration type

data Points = Point Float Float  -- typle type, based on Float

type Name = String
type MatrNr = Int
data StudId = Stud Name MatrNr
                        -- record type, based on type synonyms

data Pairs a = Pair a a
                -- polymorphic type, based on arbitrary type a

data Union a b = Fst a | Snd b
               -- union type, based on arbitrary types a and b

data Tree a = Inner a (Tree a) (Tree a) | Leaf a
                                 -- recursive polymorphic type

\{-
Main> :t Stud "Franz Gans" 4711
Stud "Franz Gans" 4711 :: StudId
Main> :t Point 0.0 0.0
Point 0.0 0.0 :: Points
Main> :t Leaf "Franz Ganz"
Leaf "Franz Ganz" :: Tree [Char]
Main> :t Fst 3.14
Fst 3.14 :: Fractional a => Union a b
Main> :t Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)
Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5) :: Num a => Tree a
Main> Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)

ERROR: Cannot find "show" function for:
*** expression : Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)
*** of type    : Tree Int
-\}
\end{code}


beachte:

\begin{itemize}
\item Großbuchstaben;
\item Typname darf als Konstruktorbezeichner verwendet werden, also zB:
\begin{code}
data Point a = Point a a
\end{code}
\end{itemize}

\textbf{Unterscheide:}

Konstruktorfunktionen und "`Programm"'-Funktionen:

\begin{enumerate}
\item Konstruktorfunktionen erlauben \emph{keine Auswertung} im Sinne
einer Reduktion auf einen einfacheren Wert; sowas wie

\begin{code}
Inner 1 (Inner 1 (Leaf 1) (Leaf 2)) (Leaf 3)
\end{code}

\emph{ist} Darstellung von

%FIXME: Bild
%Zusätzliche html-Umgebung wegen Positionierung
\begin{latexonly}
\begin{code}
     4
    / {\bkslash}
   1   3
  / {\bkslash}
 1   2 
\end{code}
\end{latexonly}

\begin{rawhtml}
<pre>    <br>
     4   <br>
    / \  <br>
   1   3 <br>
  / \    <br>
 1   2   <br>
</pre>
\end{rawhtml}

Situation ist völlig analog zu \emph{eingebauten} Datentypen, außer daß die
keine Wortsymbole verwenden, zB: : und [] für Listen.

\item Konstruktoren dürfen in \emph{patterns} auftreten und erlauben so die 
Definition von Funktionen über dem Datentyp.
\end{enumerate}

\begin{code}
-------------------------------------------some Tree functions

data Tree a = Inner a (Tree a) (Tree a) | Leaf a
                                 -- recursive polymorphic type

miniTree = Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)

listInorderTree :: (Show a) => Tree a -> String
listInorderTree (Leaf x) = show x
listInorderTree (Inner x yt zt)
      = "<" ++ (listInorderTree yt) ++
                  "<" ++ (show x) ++ ">" ++
                           (listInorderTree zt) ++ ">"

\{-
Main> listInorderTree miniTree
"<<3<2>4><1>5>"
-\}

sizeOfTree :: Tree a -> Int
sizeOfTree (Leaf x) = 1
sizeOfTree (Inner x yt zt) = 1 + (sizeOfTree yt) + (sizeOfTree zt)


mapTree :: (a->b) -> Tree a -> Tree b
mapTree f (Leaf x) = Leaf (f x)
mapTree f (Inner x yt zt) = (Inner (f x) (mapTree f yt) (mapTree f zt))

\{-
Main> listInorderTree miniTree
"<<3<2>4><1>5>"
Main> sizeOfTree miniTree
5
Main> listInorderTree (mapTree (*100) miniTree)
"<<300<200>400><100>500>"
-\}

\end{code}

Beispiel:
\begin{code}
--------------------------------------SuchBaeme

data Ord a => STree a = Node a (STree a) (STree a) | Nil
        -- polymorphic tree type with constrained on base type
        -- note: empty leaves

insertSTree :: Ord a => a -> STree a -> STree a
insertSTree x Nil = Node x Nil Nil
insertSTree x (Node y left right)
   | x<=y       = Node y (insertSTree x left) right
   | otherwise  = Node y left (insertSTree x right)

elemSTree :: Ord a => a -> STree a -> Bool
elemSTree x Nil = False
elemSTree x (Node y left right)
   | x==y       = True
   | x<y        = elemSTree x left
   | otherwise  = elemSTree x right

listToSTree :: Ord a => [a] -> STree a
listToSTree = foldr insertSTree Nil

sTreeToList :: Ord a => STree a -> [a]
sTreeToList Nil = []
sTreeToList (Node x left right)
   = (sTreeToList left) ++ [x] ++ (sTreeToList right)

miniList = [1,5,-3,6,0,99,4,4,55,1000,-1000]

\{-
Main> :t Node 3.14 Nil Nil
Node 3.14 Nil Nil :: (Ord a, Fractional a) => STree a
Main> :t Node cos Nil Nil

ERROR: a -> a is not an instance of class ``Ord''
Main> elemSTree 0 (listToSTree miniList)
True
Main> elemSTree 77 (listToSTree miniList)
False
Main> (sTreeToList.listToSTree) miniList  -- sort!
[-1000, -3, 0, 1, 4, 4, 5, 6, 55, 99, 1000]
Main> (sTreeToList.listToSTree) (map abs miniList)
[0, 1, 3, 4, 4, 5, 6, 55, 99, 1000, 1000]
-\}
\end{code}


\section{Abstrakte Datentypen}

= \emph{verberge} (verbiete Benutzung von) \emph{Konstruktion} der
Typelemente

Lösung in Haskell: Konventionell, nämlich:
\begin{itemize}
\item verpacke Typdefinition + einschlägige Operationsdefinitionen in 
\emph{Modul}
\item \emph{exportiere nur} das, was der Anwender benutzen soll, also zB 
Typ- und Operationsbezeichner in "`Exportliste"'.
\end{itemize}

$\Rightarrow$ Seite \pageref{adt_module_bsp}

\begin{wichtig}
Haskells Modulkonzept wird von verschiedenen Hugs-Versionen nicht 
(vollständig) unterstützt;
umgekehrt bieten Gofer/Hugs Systemeigene (nicht-Haskell) Syntax für
abstrakte Datentypen.
\end{wichtig}

\begin{code}
\label{adt_module_bsp}
---------------------------------------------------------ADT module
module Searchtree(STree, listToSTree, sTreeToList) where

data Ord a => STree a = Node a (STree a) (STree a) | Nil

insertSTree :: Ord a => a -> STree a -> STree a
insertSTree x Nil = Node x Nil Nil
insertSTree x (Node y left right)
   | x<=y       = Node y (insertSTree x left) right
   | otherwise  = Node y left (insertSTree x right)

listToSTree :: Ord a => [a] -> STree a
listToSTree = foldr insertSTree Nil

sTreeToList :: Ord a => STree a -> [a]
sTreeToList Nil = []
sTreeToList (Node x left right)
   = (sTreeToList left) ++ [x] ++ (sTreeToList right)



--------------------------------------client module (separate file)

module Main where
import Searchtree           -- improt complete export of Searchtree

----------------------------------------------------------use e.g.:

\{-
Prelude> :l Main.hs
Reading file "Main.hs":
Reading file "Searchtree.hs":
Reading file "Main.hs":

Hugs session for:
/usr/local/share/hugs/lib/Prelude.hs
Searchtree.hs
Main.hs
Main> (sTreeToList.listToSTree) [1,-1,0,2,-2]
[-2, -1, 0, 1, 2]
Main> sTreeToList (insertSTree 2 Nil)  --insertSTree is hidden!
ERROR: Undefined variable "insertSTree"
Main> sTreeToList Nil                  -- constructors are hidden!
ERROR: Undefined constructor function "Nil"
-\}

\end{code}


\section{Klassen}

sind in Haskell \emph{Typklassen}, dh Kollektionen von Typen, die durch 
einen \emph{gemeinsamen} Satz von \emph{Operationen} ausgezeichnet sind.

Idee aus der \emph{OO-Welt}, aber in Haskell:

\begin{itemize}
\item sowieso keine Objekte (mit änderbarem Zustand), sondern nur Werte
\item nicht dynamische ("`runtime"') Bindung einer Funktion, sondern
Typüberprüfung zur compile-time


\item viele OO-Sprachen verwenden "`Klasse"' wie "`Typ"', in Ada ähnlich wie
in Haskell:

"`Klasse"' = Familie von Typen, nämlich Definitionshierarchie

\item Klassendefinitionen in Haskell sind normalerweise \emph{abstrakt}
(nur Interfaces, allerdings defaults für Funktionen möglich) und
enthalten jedenfalls keine "`Daten"'-Definitionen

\item \emph{Klassen} können haben
\begin{itemize}
\item "`instances"' (Exemplare), dh Typen, die zur Klasse gehören
\item "`subclasses"' (abgeleitete Klassen), dh Klassen, die die Operationen
der Oberklassse "`erben"'.

\begin{wichtig}
\begin{tabular}{lcl}
instance & = & Typ \\
subclass & = & class, dh Menge von Typen
\end{tabular}
\end{wichtig}
\end{itemize}


\item es gibt Sortiment von vordefinierten Klassen wie zB Eq, Ord, Num, Show,
Read u.a., die man typisch verwendet um

\begin{enumerate}
\item bei \emph{überladenen} Funktionen den Polymorphismus sinnvoll
einzuschränken, dh die zulässige Auswahl von Typen anzugeben, zB:

\begin{code}
quicksort :: Ord a => [a]->[a]
             {\bkslash}---/
             Kontextklausel: a muß Instanz von Ord sein (mittelbar)
\end{code}

\item bei der Neueinführung von \emph{Datentypen} eine 
"`\emph{Grundausstattung}"' mit \emph{Operationen} herzustellen, zB:
Datentyp zur Instanz von "`Eq"' machen.
\end{enumerate}

\item zu vordefinierten Klassen siehe Report, zB:

\begin{code}
class Eq a
   where (==), (/=) :: a->a->Bool
         x/=y = not (x==y)  -- dh default für /=
\end{code}

Beispiel für \emph{Unterklasse} von Eq ist Ord, die zu ``=='' noch die
Operationen ``$<$, $<=$, $>=$, $>$'' sowie die Funktionen ``min, max'' 
(und noch eine Funktion ``compare'' die ein symbolisches Ergebnis liefert) 
definiert.

Beispiel von \emph{Instanzen} von Eq gibt's massenhaft, zB Int.

\end{itemize}

Beispiel: benutzerdefinierter Datentyp als Instanz von Eq:

\begin{code}
--------------------------------------old defs do not support "=":

data PrimaryColour = Yellow | Red | Blue

---------------------------------------------------as is shown by:
\{-
Main> Yellow == Blue

ERROR: PrimaryColour is not an instance of class "Eq"
-\}

-------------------------so make new type an instance of class Eq:

data PrimaryColour = Yellow | Red | Blue
instance Eq PrimaryColour
   where Yellow == Yellow = True
         Red == Red       = True
         Blue == Blue     = True
         _ == _           = True

-----------------------------------------------------which allows:
\{-
Main> Yellow == Blue
False
-\}


-------------------------------------this can be done more simply:

data PrimaryColour = Yellow | Red | Blue deriving Eq

---------------------------------------------which gives the same:
\{-
Main> Yellow == Blue
False
Main> Yellow /= Blue
True
-\}

---------but other defs of "==" could be useful for colour blinds:

data PrimaryColour = Yellow | Red | Blue
instance Eq PrimaryColour
   where _ == _ = True

-----------------------------------------------------------giving:
\{-
Main> Yellow == Blue
True
-\}
\end{code}


Beispiel: Definition einer Klasse und zweier Instanzen

\begin{code}
--------------------------------------now define your own classes:

class Mail m
   where giveAdr:: m->String
         setAdr:: String->m->m
         existsAdr:: m->Bool
         existsAdr x = (giveAdr x /= "")        -- default

data SimpleLetter a = SL String a        -- hat eine Adresse
instance Mail (SimpleLetter a)
   where giveAdr (SL s _) = s
         setAdr s (SL s' x) = (SL s x)

data BroadcastLetter a = BC [String] a   -- hat Liste von Adressen
clearAdr:: (BroadcastLetter a)->(BroadcastLetter a)
clearAdr (BC ss x) = BC [] x

instance Mail (BroadcastLetter a)
   where giveAdr (BC [] _)     = ""
         giveAdr (BC (s:ss) _) = s
         setAdr s (BC ss x) = BC (s:ss) x

---------------------------------------------------------examples:
\{-
Main> existsAdr (SL "Grete" (25, "Now", 1997))
True
Main> giveAdr(setAdr "Gustav" (setAdr "Franz"
(SL "Grete" (25, "Nov", 1997))))
"Gustav"
Main> giveAdr (clearAdr (BC ["Grete"] (25, "Nov", 1997)))
""
Main> existsAdr (clearAdr (BC ["Grete"] (25, "Nov", 1997)))
False
-\}
\end{code}


\begin{appendix}

\chapter{Übungen}

Im Proseminar Programmieren III wurden im Wintersemester 1997/98 folgende
Hausübungen aufgegeben.


\section{Blatt 1}

\begin{enumerate}

\item Machen Sie sich mit der Bedienung von Hugs und den begleitenden
Dokumenten vertraut. Wenn gewünscht, kopieren Sie das Material und 
installieren Sie das System daheim.

\item Geben sie die folgenden Ausdrücke ein und korrigieren Sie im Falle von 
Fehlermeldungen die Syntax:

\begin{code}
   max 3 4
   negate 3
   3 `div` 4
   div 3 4
   div 3 -4
   3/4
   2**3 - 4
   2 ** -3
   2 **-3
   fromIntegral 3 + 3.999
   max 3.0 4
   2 <= 3 || true
   False ==  (2 <= 3)
   "ABC" == ['A','B','C']
   "A" = 'A'
   "A" =='A'
   let x = 'A' in x:"BC"
   let x = "A" in x == x
   let x = "A" in x /= x
   let x = "A" in not x == x
   let x = "A" in not (x == x)
   not (let x = "A" in x == x)
   let y = not (let x = "A" in x == x) in not y
\end{code}

   Informieren Sie sich in Anhang A, Standard Prelude, des Haskell Reports
über Standardfunktionen und ihren Gebrauch und bilden Sie ähnliche Beispiele.


\item Schreiben Sie ein Haskell-Skript, das Funktionen zur Berechnug der 
Fläche einiger geometrischer Figuren enthält.
\end{enumerate}


\section{Blatt 2}

\begin{enumerate}

\item Experimentieren Sie mit arithmetischen Ausdrücken und machen Sie sich 
die dabei zur Anwendung kommenden Regeln klar ($\Rightarrow$ Literatur); befassen Sie 
sich insbesondere mit Klammerung, Typfragen (Mischung von Float und Int), 
Grenzen des Zahlbereichs.

\item Geben sie eigene Haskell Definitionen (nebst Typ) für übliche Funktionen
wie Fakultät, Fibonacci, ggT, max, k-aus-n und dergleichen, und probieren Sie 
die Eigenprodukte aus.

\item Geben sie eigene Haskell Definitionen für "`und"' und "`oder"' durch 
Fallunterscheidung (ohne Gebrauch der vorgegebenen Operationen) . Prüfen Sie 
anhand von Beispielen, ob Ihre Eigenprodukte mit ``\texttt{\&\&}'' und ``\texttt{||}'' 
übereinstimmen hinsichtlich a) des Verhaltens im Falle undefinierter/fehlerhafter 
Teilausdrücke (sowas wie \texttt{True || (1/0) == 0.001} ) und b) der 
Bindekraft-/Assoziationsregeln. Wenn nicht: Kann man da was machen?

\item Schreiben Sie eine Funktion 
\texttt{integrate :: (Float->Float)->Float->Float}, die bei Aufruf mit \\ 
\texttt{integrate f x} den Wert des Integrals von f  im Intervall von 0 bis x
liefert. Benutzen Sie zur Berechnung ein einfaches Näherungsverfahren 
(Unterteilung in eine feste oder auch von der Intervallbreite abhängige Zahl 
von Streifen).

\item Verändern Sie das in der Vorlesung gegebene Verfahren zur 
Nullstellenberechnug in ein Verfahren zur Berechnung der n-ten Wurzel einer 
Zahl x (n :: Int, n$>$1, x:: Float). Das neue Verfahren soll im Unterschied zum 
alten n und nicht eine reelle Funktion als Parameter haben, und es soll bei 
der Formulierung des Verbesserungsschritts nicht von numerischer 
Differentiation (also der Funktion diff) Gebrauch machen, sondern die 
jedermann bekannte Ableitung der Funktion x\^n benutzen.
\end{enumerate}


\section{Blatt 3}

\begin{enumerate}

\item Das Hugs-System informiert bei entsprechender Einstellung (Kommando 
":set +s") über den bei Auswertung eines Ausdrucks anfallenden Aufwand an 
Berechnungsschritten ("`reductions"') und Speicherplatz ("`cells"'). 
Eine genaue und vollständige Interpretation der gelieferten Zahlenwerte ist 
nicht ganz einfach; sie geben aber auch ohne detailliertes Verständnis der 
Arbeit der Haskell-Maschine eine brauchbare Vorstellung von der Effizienz von 
Funktionsdefinitionen etc. --- Informieren Sie sich über diese Option und 
probieren Sie sie anhand der fogenden Aufgaben und auch anderer Beispiele aus!

\item Die n-te Potenz einer Zahl k ist zu berechnen nach den beiden folgenden 
(in ihrer Effizienz sehr verschiedenen, vgl. Prog 1) Methoden:

\begin{enumerate}
\item wiederholtes Multiplizieren von k
\item wiederholtes Quadrieren (unter Halbieren des Exponenten).
\end{enumerate}

Hinweis: Beim Testen verlässt man leicht den implementierten Zahlbereich, was 
zu einem falschen Ergebnis (ohne Fehlermeldung) führen kann; wenn Sie große 
Exponenten ausprobieren, sollten Sie deshalb die triviale Basis 1 verwenden. 
Dabei gibt es dann noch die Möglichkeit, daß das System die Menge der 
unfertigen rekursiven Aufrufe nicht mehr bewältigen kann. Welche 
Fehlermeldung ergibt sich dann?

\item Ein Geldbetrag b sei zu wechseln, d.h. in gebräuchlichen 
Münzeinheiten (gegeben in einer Liste [m1, m2, ..mn] von Zahlenwerten)
darzustellen.

\begin{enumerate}
\item Definieren Sie eine Funktion, die Betrag und Münzwertliste als Parameter
hat und eine Darstellung (in Form einer Liste mit Münzanzahlen) des Betrags 
mit möglichst wenig Münzen liefert. (Nehmen Sie an, daß die Münzwertliste 
absteigend sortiert sei.)

\item Definieren Sie eine Funktion, die Betrag und Münzwertliste als Parameter
hat und die Zahl aller möglichen Darstellungen des Betrags errechnet. 
Verwenden sie dazu die offensichtliche (?) Rekursion:

Anzahl für b und Münzwertliste [m1, m2, ..mn]  = \\
   Anzahl für b und Münzwertliste [m2, ..mn] + Anzahl für b-m1 und 
Münzwertliste [m1, m2, ..mn].
\end{enumerate}

\end{enumerate}


\section{Blatt 4}

\begin{enumerate}

\item Tupel (z.B. geordnete Paare, Tripel, Quadrupel, \dots ) sind wie Listen für alle 
möglichen Elementtypen definiert, haben aber jeweils feste Länge und können auch 
Elementtypen mischen, also die Aufgabe von records in anderen Sprachen übernehmen. 
Notation (für Typ und Elemente): runde Klammern, also z.B.:

\begin{code}
()              -- nix drin !!
(4711)          -- wird mit Zahl 4711 identifiziert
(-1.0,1.0)
(sin,cos)
(sin 0,cos 0)
("Franz Gans", (30,"Okt",1950), "Salzburg")
\end{code}

\begin{enumerate}
\item Stellen Sie den Typ dieser Beispiele fest.
\item Für Paare gibt es vordefinierte Projektionsfunktionen fst und snd auf die beiden 
Komponenten; definieren Sie entsprechende Funktionen für Tripel.
\item Die explizite Angabe von Tupeltypen ist oft mühsam (vgl. a)). Haskell erlaubt die 
Einführung von Typsynonymen, d.h. benutzerdefinierte Namen für vorhandene 
Typkonstruktionen. (Das ist wohlgemerkt die Einführung einer bequemeren Bezeichnung und 
nicht eines neuen Typs!!)

Beispiel: \texttt{type Point = (Float,Float) ; type Rectangle = Point,Point,Point,Point)}.

Geben Sie Definitionen für typische Datensätze wie z.B. für Personen oder 
Bibliotheksbücher zusammen mit einem Typsynonym,  Projektionsfunktionen auf Komponenten 
und ein paar weitere sinnvolle Funktionen (z.B. aktuelles Alter einer Person, 
Anschriftänderung).
\end{enumerate}

\item Sind zu einer Funktion f zwei Argumentwerte a und b mit f(a) $<$ 0 $<$ f(b) 
bekannt, so kann man eine Nullstelle durch wiederholte Halbierung des Intervalls 
suchen. Definieren Sie eine entsprechende Funktion unter Verwendung der 
``until''-Funktion (Vorlesung oder Prelude) sowie von Float-Paaren für Intervalle.

\item Brüche lassen sich als Int-Paare darstellen. Geben Sie Definitionen von 
Funktionen für die vier Grundrechenarten für Brüche sowie eine Normalisierungsfunktion, 
die einen Bruch auf die übliche gekürzte Form mit positivem Nenner bringt.

\end{enumerate}


\section{Blatt 5}

Bei den folgenden Aufgaben sollen Sie Gebrauch machen von Standardfunktionen zur 
Listenverarbeitung wie take, map, fold, filter, \dots

\begin{enumerate}
\item Geben Sie so eine neue Definition der ``how\_many'' Funktion des Beispiels aus 3.3.

\item Eine Liste wird sortiert, indem man sie in zwei (im Idealfall gleich große) 
Teillisten zerlegt, diese (nach demselben Verfahren) sortiert und dann wieder in 
geeigneter Weise vereinigt, z.B.:

\begin{enumerate}
\item merge sort:

Teilung = Halbierung der Liste,\\
Vereinigung = ordnungstreue Verzahnung (``merge'') der beiden sortierten Listen.

\item quick sort:

Teilung durch Vergleich mit Trennelement (z.B. erstes Element der Liste),\\
Vereinigung durch Konkatenation der sortierten Listen.

(Hinweis: man kann die Aufspaltung mit zwei ``filter'' Anwendungen, aber vielleicht 
auch in einem Durchlauf machen).
\end{enumerate}

\item Um die Liste aller Permutationen einer Liste x:xs zu berechnen (das ist dann eine 
Liste von Listen), kann man wie folgt vorgehen:

erstens, finde alle Permutationen von xs,\\
zweitens, setze x auf alle denkbaren Weisen in jede der Permutationen ein.

\end{enumerate}


\section{Blatt 6}

\begin{enumerate}

\item Verwenden Sie die in der Vorlesung definierten Funktionen zur Lösung eines 
nichttrivialen Layout-Beispiels.

\item Definieren Sie eine Funktion \texttt{asCBlock:: Int->Int->[Line]->Block}, in 
deren Resultat Textzeilen zentriert vorliegen, und geben Sie eine Beispielanwendung.

\item Bei einem Text soll für jedes vorkommende Wort die Häufigkeit seines 
Vorkommens ermittelt und in einer lexikographisch geordneten (Wort, Häufigkeit)-Liste 
ausgegeben werden. Verwenden Sie die Textanalyse-Funktionen der Vorlesung, aber lassen 
Sie dann als zu zählendes Wort nur eine Zeichenreihe gelten, die mit einem 
Alphabetzeichen beginnt. Damit die Zählung sinnvoll ist, entfernen Sie am Ende eines 
Wortes auch noch allfällige Satzzeichen. (Also: ``4711'' oder ``:='' gilt nicht, 
``DIN-A4'' gilt, ``Kaffee?'' gilt als ``Kaffee'').

\end{enumerate}

\chapter{Proseminar-Tests}

\section{Test 1}

Die folgenden Aufgaben präsentieren Haskell-Ausdrücke, für die Sie jeweils den Wert
angegeben sollen oder aber ob ein Syntax-, Typ- oder Laufzeitfehler vorliegt. 
(Vermerken Sie Ihre Antwort bitte auf diesem Blatt hinter dem Ausdruck und verwenden 
Sie für die drei Fehlerfälle die Abkürzungen SF, TF, LF !) Es wird der übliche Kontext 
(standard prelude) angenommen.

\begin{enumerate}

\item
\begin{code}
   max 3 4                        negate 3
   3 `div` 4                      div 3 4
   div 3 -4                       2**3 - 4
   True && (1/0 == 0)             False ==  (2 <= 3)
   "A" = 'A'                      "A" == 'A'
   "ABC" == ['A','B','C']

   let x = 'A' in x:"BC"          let x = "A" in x == x
   let x = "A" in x /= x  
   let x = "A" in not x == x
   let x = "A" in not (x == x)
\end{code}

\item Zur Erinnerung: Die Funktion max liefert den größeren zweier Zahlenwerte, und die
polymorphe Identitätsfunktion id ist definiert durch \texttt{id:: a->a} und 
\texttt{id x = x}.

Untersuchen Sie:

\begin{code}
   (id.max)3 2          (id.max 3) 2          id.(max 3) 2
   id max 3 2           id (max 3) 2          (id max) 3 2
   (id max 3) 2         id (max 3 2)          max id 3 2
\end{code}

\item Die Funktion f sei definiert als:

\begin{code}
   f:: (Int->Int->Int)->Int->[Int]->Int
   f g e []     = e
   f g e (x:xs) = g x (f g e xs)
\end{code}

Untersuchen Sie:

\begin{code}
   f max 5 [4,3,2,1]
   f div 1 [5,4,3,2]
\end{code}

\end{enumerate}


\section{Test 2}

Die Aufgaben 1 und 2 präsentieren Haskell-Ausdrücke, für die Sie jeweils den Wert 
angegeben sollen oder aber ob ein Syntax-, Typ- oder Laufzeitfehler vorliegt. 
(Vermerken Sie Ihre Antwort bitte auf diesem Blatt hinter dem Ausdruck und verwenden 
Sie für die drei Fehlerfälle die Abkürzungen SF, TF, LF !) Es wird der übliche 
Kontext (standard prelude) angenommen.

\begin{enumerate}

\item
\begin{code}
   True || (1/0 == 0)          False == True && (1/0 /= 0)
   True && 0 * (1/0)           False && 1/0
   False || (True || (1/0 > 0))
   let x = 1/(x - 1) in x == 1
\end{code}

\item Gegeben:

\begin{code}
   fix:: (Float->Float)->Float->Float
   fix f = repeat_until pred f
             where pred x = (abs(f x - x) <= 0.01)
   square:: Float->Float
   square x = x*x
\end{code}

Was ist (ungefähr):

\begin{code}
   fix square 0.01
   fix square 0.1
   fix square 1.0
\end{code}

\item Die folgende Funktion soll feststellen, ob eine Liste den Anfang einer anderen 
bildet. Komplettieren Sie den dritten Fall der Definition (ohne weitere 
Fallunterscheidung!!).

\begin{code}
   initial_part:: [a]->[a]->Bool
   initial_part [] _ = True
   initial_part _ [] = False
   initial_part (x:xs) (y:ys) = 
\end{code}

\item Die Funktion \texttt{double:: Float->Float} sei definiert als 
\texttt{double x = 2 * x}. Geben Sie die Auswertungsschritte unter lazy evaluation 
für den Ausdruck

\begin{code}
double (double (1+1)) =>
\end{code}

\end{enumerate}

\section{Test 3}

Die Aufgaben 1 und 2 präsentieren Haskell-Ausdrücke, für die Sie jeweils den Wert 
angeben sollen oder aber ob ein Syntax-, Typ- oder Laufzeitfehler vorliegt. 
(Vermerken Sie Ihre Antwort bitte auf diesem Blatt hinter dem Ausdruck und verwenden 
Sie für die drei Fehlerfälle die Abkürzungen SF, TF, LF !) Es wird der übliche Kontext 
(standard prelude) angenommen.

\begin{enumerate}

\item
\begin{code}
   [[]] ++ [2] == [2]               [[]] ++ [2] == [[2]]
   [[]] ++ [2] == [[],[2]]          [[]] ++ [[2]] == [[],[2]]
   [[2]] ++ [] == [[2]]             [[2]] ++ [[2]] == [[2]]
   [[2]] ++ [[2]] == [[2],[2]]      [[2]] ++ [] == [[2],[]]
\end{code}

\item Gegeben sind die Funktionen aus der Vorlesung: \texttt{asLines:: Text->[Line]}, 
\texttt{asWords:: Line->[Word]}, \texttt{asParas:: [Line]->[Para]} sowie die Definition 
\texttt{beisp = "{}ab{\bkslash}nx{\bkslash}n"}. Was ist:

\begin{code}
(map(map asWords).asParas.asLines) beisp
(asParas.(map asWords).asLines) beisp
(length.concat.map asWords) (asLines beisp)
map (length.concat.map asWords) (asParas (asLines beisp))
\end{code}


\item Im folgenden soll eine alternative Definition  der Konkatenation gegeben werden. 
Ergänzen Sie die fehlenden Teile (ohne Verwendung von \texttt{(++)}, d.h. ohne explizite 
Rekursion):

\begin{code}
   (++):: [a]->[a]->[a]
   xs ++ ys = foldr op a b
              where op =
                     a =
                     b =
\end{code}

\item Die Funktion \texttt{subs} sei definiert als

\begin{code}
   subs [] = [[]]
   subs (x:xs) = subs xs ++ map (x:) (subs xs) 
\end{code}

\begin{enumerate}
\item Welche der folgenden Typdeklarationen paßt dazu:

\begin{code}
subs:: [a]->[a]                 subs:: [a]->[[a]]
subs:: [[a]]->[a]               subs:: [[a]]->[[a]]
\end{code}

\item Was ist: \texttt{subs [[1,2],[9]]}

\end{enumerate}

\end{enumerate}


\end{appendix}

\end{document}