Block / Neumann Haskell-Intensivkurs

Ein kompakter Einstieg in die funktionale Programmierung
1. Auflage 2011
ISBN: 978-3-642-04718-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 300 Seiten

Reihe: Computer Science and Engineering (German Language)

Das Buch bietet eine kompakte Einführung in die funktionale Programmierung mit Haskell. Zunächst werden grundlegende Konzepte anhand von anschaulichen Beispielen vermittelt, die das Fundament für die funktionale Programmentwicklung bilden. Anschließend werden fortgeschrittene Aspekte behandelt, um das Verständnis weiter zu vertiefen. Mit zahlreichen Anwendungen und Themengebieten, die gemeinsam mit dem Leser erarbeitet werden, durchstreifen die Autoren verschiedene Bereiche der Informatik. Am Ende jedes Kapitels werden die behandelten Themen mit Übungsaufgaben gefestigt. Durch die vorhandenen Lösungen am Ende des Buches wird ein Selbststudium ermöglicht. Auf der Webseite von Springer sind die Buchbeispiele und weitere Materialien zu finden.

Autoren/Hrsg.

Block, Marco

Neumann, Adrian

Inhaltsverzeichnis

1;1 Motivation und Einführung;20
1.1;1.1 Funktionale Programmierung;21
1.1.1;1.1.1 Motivation und Anwendung;21
1.1.2;1.1.2 Warum gerade Haskell?;22
1.2;1.2 Grundbegriffe und Prinzipien der Programmentwicklung;22
1.3;1.3 Installation und Verwendung von Haskell;23
1.3.1;1.3.1 Installation der aktuellen Version;24
1.3.2;1.3.2 Die ersten Schritte in Hugs;25
1.3.3;1.3.3 Arbeiten auf der Konsole;25
1.3.4;1.3.4 Die Entwicklungsumgebung winhugs;26
1.3.5;1.3.5 Erstellung und Verwendung von Skripten;27
1.4;1.4 Haskell ist mehr als ein Taschenrechner;28
1.5;1.5 Vordefinierte Funktionen der Prelude;29
2;Teil I Haskell-Grundlagen;31
2.1;2 Einfache Datentypen;32
2.1.1;2.1 Wahrheitswerte;33
2.1.1.1;2.1.1 Negation;34
2.1.1.2;2.1.2 Konjunktion;34
2.1.1.3;2.1.3 Disjunktion;35
2.1.1.4;2.1.4 Exklusiv-Oder;35
2.1.1.5;2.1.5 Boolesche Algebra;36
2.1.1.6;2.1.6 Boolesche Gesetze;36
2.1.2;2.2 Zahlentypen;38
2.1.2.1;2.2.1 Datentyp Int;38
2.1.2.2;2.2.2 Datentyp Integer;39
2.1.2.3;2.2.3 Datentypen Float und Double;40
2.1.3;2.3 Zeichen und Symbole;40
2.1.4;2.4 Übungsaufgaben;41
2.2;3 Funktionen und Operatoren;42
2.2.1;3.1 Funktionen definieren;43
2.2.1.1;3.1.1 Parameterübergabe;44
2.2.1.2;3.1.2 Reservierte Schlüsselwörter;45
2.2.1.3;3.1.3 Wildcards;45
2.2.1.4;3.1.4 Signaturen und Typsicherheit;46
2.2.1.5;3.1.5 Pattern matching;47
2.2.1.6;3.1.6 Pattern matching mit case;48
2.2.1.7;3.1.7 Lokale Definitionen mit where;48
2.2.1.8;3.1.8 Lokale Definitionen mit let-in;49
2.2.1.9;3.1.9 Fallunterscheidungen mit Guards;50
2.2.1.10;3.1.10 Fallunterscheidungen mit if-then-else;51
2.2.1.11;3.1.11 Kommentare angeben;51
2.2.2;3.2 Operatoren definieren;52
2.2.2.1;3.2.1 Assoziativität und Bindungsstärke;52
2.2.2.2;3.2.2 Präfixschreibweise – Operatoren zu Funktionen;53
2.2.2.3;3.2.3 Infixschreibweise – Funktionen zu Operatoren;54
2.2.2.4;3.2.4 Eigene Operatoren definieren;54
2.2.3;3.3 Lambda-Notation;55
2.2.4;3.4 Übungsaufgaben;56
2.3;4 Rekursion als Entwurfstechnik;57
2.3.1;4.1 Rekursive Fakultätsfunktion;58
2.3.2;4.2 Lineare Rekursion;59
2.3.3;4.3 Kaskadenförmige Rekursion;60
2.3.4;4.4 Verschachtelte Rekursion;61
2.3.5;4.5 Wechselseitige Rekursion;62
2.3.6;4.6 Endständige Rekursion;62
2.3.7;4.7 Übungsaufgaben;62
2.4;5 Einfache Datenstrukturen;64
2.4.1;5.1 Listen;65
2.4.1.1;5.1.1 Zerlegung in Kopf und Rest;66
2.4.1.2;5.1.2 Rekursive Listenfunktionen;68
2.4.1.3;5.1.3 Zusammenfassen von Listen;70
2.4.1.4;5.1.4 Automatische Erzeugung von Listen;71
2.4.1.5;5.1.5 Automatisches Aufzählen von Elementen;72
2.4.1.6;5.1.6 Lazy evaluation;74
2.4.1.6.1;5.1.6.1 Unendliche Listen;74
2.4.1.6.2;5.1.6.2 Das Sieb des Eratosthenes;75
2.4.1.7;5.1.7 Listen zerlegen;76
2.4.2;5.2 Tupel;77
2.4.2.1;5.2.1 Beispiel pythagoräisches Tripel;78
2.4.2.2;5.2.2 Beispiel n-Dameproblem;79
2.4.3;5.3 Zeichenketten;80
2.4.4;5.4 Übungsaufgaben;82
2.5;6 Funktionen höherer Ordnung;83
2.5.1;6.1 Mapping;85
2.5.2;6.2 Filtern;86
2.5.3;6.3 Faltung;87
2.5.3.1;6.3.1 Faltung von rechts mit Startwert;88
2.5.3.2;6.3.2 Faltung von rechts ohne Startwert;91
2.5.3.3;6.3.3 Faltung von links mit Startwert;92
2.5.3.4;6.3.4 Faltung von links ohne Startwert;93
2.5.3.5;6.3.5 Unterschied zwischen Links- und Rechtsfaltung;93
2.5.4;6.4 Entfaltung;94
2.5.4.1;6.4.1 Definition von unfold;94
2.5.4.2;6.4.2 Mapping durch unfold;95
2.5.5;6.5 Zip;96
2.5.6;6.6 Unzip;96
2.5.7;6.7 Funktionskompositionen;97
2.5.8;6.8 Currying;99
2.5.9;6.9 Übungsaufgaben;101
2.6;7 Eigene Typen und Typklassen definieren;102
2.6.1;7.1 Typsynonyme mit type;103
2.6.2;7.2 Einfache algebraische Typen mit data und newtype;104
2.6.2.1;7.2.1 Datentyp Tupel ;107
2.6.2.2;7.2.2 Datentyp Either;107
2.6.2.3;7.2.3 Datentyp Maybe ;108
2.6.2.4;7.2.4 Datentypen mit mehreren Feldern;109
2.6.3;7.3 Rekursive Algebraische Typen;111
2.6.4;7.4 Automatische Instanzen von Typklassen;112
2.6.4.1;7.4.1 Typklasse Show ;113
2.6.4.2;7.4.2 Typklasse Read;113
2.6.4.3;7.4.3 Typklasse Eq ;114
2.6.4.4;7.4.4 Typklasse Ord;114
2.6.4.5;7.4.5 Typklasse Enum ;114
2.6.4.6;7.4.6 Typklasse Bounded ;115
2.6.5;7.5 Eingeschränkte Polymorphie;115
2.6.6;7.6 Manuelles Instanziieren;115
2.6.7;7.7 Projekt: Symbolische Differentiation;118
2.6.7.1;7.7.1 Operatorbaum;119
2.6.7.2;7.7.2 Polynome berechnen;120
2.6.7.3;7.7.3 Ableitungsregeln;120
2.6.7.4;7.7.4 Automatisches Auswerten;121
2.6.8;7.8 Eigene Klassen definieren;122
2.6.9;7.9 Übungsaufgaben;123
2.7;8 Modularisierung und Schnittstellen;124
2.7.1;8.1 Module definieren;125
2.7.2;8.2 Sichtbarkeit von Funktionen;125
2.7.3;8.3 Qualified imports;127
2.7.4;8.4 Projekt: Adressbuch;127
2.7.4.1;8.4.1 Modul Woerterbuch;127
2.7.4.2;8.4.2 Modul Adressbuch;128
2.7.4.3;8.4.3 Modul TestAdressbuch;129
2.7.5;8.5 Übungsaufgaben;130
3;Teil II Fortgeschrittene Haskell-Konzepte;132
3.1;9 Laufzeitanalyse von Algorithmen;133
3.1.1;9.1 Motivation;134
3.1.2;9.2 Landau-Symbole ;135
3.1.2.1;9.2.1 Obere Schranken O;135
3.1.2.2;9.2.2 Starke obere Schranken o;136
3.1.2.3;9.2.3 Untere Schranken ;136
3.1.2.4;9.2.4 Starke untere Schranken ;137
3.1.2.5;9.2.5 Asymptotisch gleiches Wachstum ;137
3.1.2.6;9.2.6 Definition über Grenzwerte von Quotientenfolgen;137
3.1.3;9.3 Umgang mit Schranken und Regeln;137
3.1.4;9.4 Übersicht wichtiger Laufzeiten;139
3.1.5;9.5 Best, Worst und Average Case;139
3.1.6;9.6 Analysieren der Laufzeit;139
3.1.6.1;9.6.1 Fakultätsfunktion;140
3.1.6.2;9.6.2 Elemente in Listen finden;141
3.1.6.3;9.6.3 Listen umdrehen;142
3.1.6.4;9.6.4 Potenzen;143
3.1.6.5;9.6.5 Minimum einer Liste;145
3.1.7;9.7 Übungsaufgaben;147
3.2;10 Arrays, Listen und Stacks;148
3.2.1;10.1 Arrays;149
3.2.1.1;10.1.1 Statische Arrays;149
3.2.1.2;10.1.2 Dynamische Arrays;151
3.2.2;10.2 Liste und Stack;152
3.2.3;10.3 Listen sortieren;153
3.2.3.1;10.3.1 SelectionSort;153
3.2.3.2;10.3.2 InsertionSort;154
3.2.3.3;10.3.3 BubbleSort;155
3.2.3.4;10.3.4 QuickSort;157
3.2.3.5;10.3.5 MergeSort;159
3.2.3.6;10.3.6 BucketSort;160
3.2.3.7;10.3.7 RadixSort;161
3.2.4;10.4 Algorithmen auf Stacks;163
3.2.4.1;10.4.1 Umgekehrte Polnische Notation;163
3.2.4.2;10.4.2 Projekt: Klammertest;164
3.2.5;10.5 Übungsaufgaben;166
3.3;11 Warteschlangen;167
3.3.1;11.1 Implementierung über Listen;168
3.3.2;11.2 Amortisierte Laufzeitanalyse;169
3.3.2.1;11.2.1 Bankiermethode;169
3.3.2.2;11.2.2 Analyse der Warteschlange;170
3.3.3;11.3 Erweiterung um Lazy Evaluation;170
3.3.4;11.4 Angepasste amortisierte Analyse;171
3.3.5;11.5 Beispielanwendung;173
3.3.6;11.6 Übungsaufgaben;173
3.4;12 Bäume;174
3.4.1;12.1 Implementierung der Datenstruktur Baum;175
3.4.2;12.2 Balancierte Bäume;176
3.4.3;12.3 Traversierungen;177
3.4.3.1;12.3.1 Pre-, In- und Postorder;177
3.4.3.2;12.3.2 Levelorder;178
3.4.4;12.4 Übungsaufgaben;179
3.5;13 Wörterbücher;180
3.5.1;13.1 Analyse und Vorüberlegungen;181
3.5.2;13.2 Implementierung;182
3.5.3;13.3 Laufzeitanalyse;183
3.5.4;13.4 Übungsaufgaben;184
3.6;14 Prioritätswarteschlangen;186
3.6.1;14.1 Operationen und mögliche Umsetzungen;187
3.6.2;14.2 Realisierung mit einer Liste;187
3.6.3;14.3 Realisierung mit einem Binärbaum;187
3.6.4;14.4 Zwei Bäume verschmelzen;189
3.6.5;14.5 Amortisierte Laufzeitanalyse von merge;190
3.6.6;14.6 Beispielanwendung;191
3.6.7;14.7 Übungsaufgaben;192
3.7;15 Random-Access Listen;193
3.7.1;15.1 Realisierung mit einem Suchbaum;194
3.7.1.1;15.1.1 Preorder versus Inorder bei Binärbäumen;194
3.7.1.2;15.1.2 Liste vollständiger Binärbäume;195
3.7.1.3;15.1.3 Verschmelzen mit Greedy-Strategie;195
3.7.2;15.2 Implementierung der grundlegenden Listenfunktionen;197
3.7.3;15.3 Implementierung von elementAn;198
3.7.4;15.4 Beispielanwendung;199
3.7.5;15.5 Übungsaufgaben;200
3.8;16 Graphen;201
3.8.1;16.1 Definition und wichtige Begriffe;202
3.8.2;16.2 Abstrakter Datentyp Graph;203
3.8.2.1;16.2.1 Adjazenzliste und Adjazenzmatrix;203
3.8.2.2;16.2.2 Implementierung der Adjazenzliste;204
3.8.3;16.3 Algorithmen auf Graphen;205
3.8.3.1;16.3.1 Traversieren von Graphen ;206
3.8.3.1.1;16.3.1.1 Tiefensuche im Graphen;207
3.8.3.1.2;16.3.1.2 Breitensuche im Graphen;208
3.8.3.1.3;16.3.1.3 Implementierung von Tiefen- und Breitensuche;208
3.8.3.2;16.3.2 Topologisches Sortieren;212
3.8.4;16.4 Übungsaufgaben;215
3.9;17 Monaden;216
3.9.1;17.1 Einführung und Beispiele;217
3.9.1.1;17.1.1 Debug-Ausgaben ;217
3.9.1.1.1;17.1.1.1 Rückgabewert und Funktionskomposition;217
3.9.1.1.2;17.1.1.2 Eigene Eingabetypen definieren;218
3.9.1.1.3;17.1.1.3 Identitätsfunktion;218
3.9.1.2;17.1.2 Zufallszahlen;219
3.9.2;17.2 Monaden sind eine Typklasse;220
3.9.3;17.3 do-Notation;221
3.9.3.1;17.3.1 Allgemeine Umwandlungsregeln;221
3.9.3.2;17.3.2 Umwandlungsregeln für if-then-else;222
3.9.3.3;17.3.3 Beispiel;223
3.9.4;17.4 Vordefinierte Monaden;224
3.9.4.1;17.4.1 Monade Writer;224
3.9.4.2;17.4.2 Monade Reader;225
3.9.4.3;17.4.3 Monade State;227
3.9.4.4;17.4.4 Monade List;229
3.9.5;17.5 Ein- und Ausgaben;231
3.9.5.1;17.5.1 Stream-basierte Eingaben;231
3.9.5.2;17.5.2 Monade IO;232
3.9.5.2.1;17.5.2.1 Bildschirmausgaben;233
3.9.5.2.2;17.5.2.2 Tastatureingaben;234
3.9.5.2.3;17.5.2.3 Eingabepufferung;234
3.9.5.2.4;17.5.2.4 Beispiel: Hangman;235
3.9.5.3;17.5.3 Dateien ein- und auslesen;237
3.9.6;17.6 Übungsaufgaben;238
3.10;18 Programme verifizieren und testen;240
3.10.1;18.1 Beweis durch vollständige Induktion;241
3.10.1.1;18.1.1 Die fünf Peano-Axiome;241
3.10.1.2;18.1.2 Beweiskonzept;242
3.10.1.2.1;18.1.2.1 Gaußsche Summenformel;242
3.10.1.2.2;18.1.2.2 Vier- und Fünf-Euro-Münze;243
3.10.1.2.3;18.1.2.3 Fakultätsfunktion;243
3.10.1.3;18.1.3 Vollständige Induktion über Strukturen;244
3.10.1.3.1;18.1.3.1 Induktion über Listen;245
3.10.1.3.2;18.1.3.2 Induktion über Bäume;246
3.10.2;18.2 QuickCheck;247
3.10.2.1;18.2.1 Beispiel: Sortieren;248
3.10.2.2;18.2.2 QuickCheck für eigene Typen verwenden;249
3.10.2.3;18.2.3 Testdatengeneratoren;249
3.10.3;18.3 Übungsaufgaben;250
3.11;19 Berechenbarkeit und Lambda-Kalkül;252
3.11.1;19.1 Der Lambda-Kalkül;253
3.11.2;19.2 Formale Sprachdefinition;253
3.11.2.1;19.2.1 Bezeichner;253
3.11.2.2;19.2.2 -Funktion;254
3.11.2.3;19.2.3 Applikation;254
3.11.2.4;19.2.4 Reguläre -Ausdrücke;254
3.11.3;19.3 Freie und gebundene Variablen;255
3.11.4;19.4 -Ausdrücke auswerten;255
3.11.4.1;19.4.1 -Konversion ;255
3.11.4.2;19.4.2 -Reduktion ;256
3.11.5;19.5 Boolesche Algebra;257
3.11.5.1;19.5.1 True und False;257
3.11.5.2;19.5.2 Negation;258
3.11.5.3;19.5.3 Konjunktion und Disjunktion;258
3.11.6;19.6 Tupel;258
3.11.6.1;19.6.1 2-Tupel;259
3.11.6.2;19.6.2 First und Second;259
3.11.7;19.7 Listen;259
3.11.7.1;19.7.1 Head – Kopf einer Liste;260
3.11.7.2;19.7.2 Tail – Rest einer Liste;260
3.11.7.3;19.7.3 Empty – Test auf eine leere Liste und Nil;260
3.11.8;19.8 Arithmetik;261
3.11.8.1;19.8.1 Natürliche Zahlen;261
3.11.8.2;19.8.2 Zero – Der Test auf Null;261
3.11.8.3;19.8.3 S – Die Nachfolgerfunktion;262
3.11.8.4;19.8.4 Die Addition;263
3.11.8.5;19.8.5 Die Multiplikation;264
3.11.8.6;19.8.6 Die Vorgängerfunktion;264
3.11.9;19.9 Rekursion;265
3.11.9.1;19.9.1 Alternative zu Funktionsnamen;265
3.11.9.2;19.9.2 Fixpunktkombinatoren;266
3.11.10;19.10 Projekt: -Interpreter;267
3.11.10.1;19.10.1 -Ausdrücke repräsentieren;268
3.11.10.2;19.10.2 Auswerten von -Ausdrücken;268
3.11.10.3;19.10.3 Freie und gebundene Variablen;270
3.11.10.4;19.10.4 Wörterbuch für Substitutionen;270
3.11.10.5;19.10.5 -Parser;272
3.11.11;19.11 Übungsaufgaben;274
4;Lösungen der Aufgaben;275
5;Literaturverzeichnis;283
6;Sachverzeichnis;286