% -*- 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 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{(, )} 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} & []\\ & []\\ & []\\ & \{\}\\ \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} 


[ [  2  3  4   5  ... ],

  [  3  5  7   9  ... ],

  [  5  7 11  13  ... ],

   ... 

                       ]
\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} 


    +-+

[ [ |2| 3  4   5  ... ],

  [ |3| 5  7   9  ... ],

  [ |5| 7 11  13  ... ],

   ... 

    +-+                ]
\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} 
    

     4   

    / \  

   1   3 

  / \    

 1   2
\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 [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}