Haskell-Intensivkurs (eBook)

1 Motivation und Einführung 20
1.1 Funktionale Programmierung 21
1.1.1 Motivation und Anwendung 21
1.1.2 Warum gerade Haskell? 22
1.2 Grundbegriffe und Prinzipien der Programmentwicklung 22
1.3 Installation und Verwendung von Haskell 23
1.3.1 Installation der aktuellen Version 24
1.3.2 Die ersten Schritte in Hugs 25
1.3.3 Arbeiten auf der Konsole 25
1.3.4 Die Entwicklungsumgebung winhugs 26
1.3.5 Erstellung und Verwendung von Skripten 27
1.4 Haskell ist mehr als ein Taschenrechner 28
1.5 Vordefinierte Funktionen der Prelude 29
Teil I Haskell-Grundlagen 31
2 Einfache Datentypen 32
2.1 Wahrheitswerte 33
2.1.1 Negation 34
2.1.2 Konjunktion 34
2.1.3 Disjunktion 35
2.1.4 Exklusiv-Oder 35
2.1.5 Boolesche Algebra 36
2.1.6 Boolesche Gesetze 36
2.2 Zahlentypen 38
2.2.1 Datentyp Int 38
2.2.2 Datentyp Integer 39
2.2.3 Datentypen Float und Double 40
2.3 Zeichen und Symbole 40
2.4 Übungsaufgaben 41
3 Funktionen und Operatoren 42
3.1 Funktionen definieren 43
3.1.1 Parameterübergabe 44
3.1.2 Reservierte Schlüsselwörter 45
3.1.3 Wildcards 45
3.1.4 Signaturen und Typsicherheit 46
3.1.5 Pattern matching 47
3.1.6 Pattern matching mit case 48
3.1.7 Lokale Definitionen mit where 48
3.1.8 Lokale Definitionen mit let-in 49
3.1.9 Fallunterscheidungen mit Guards 50
3.1.10 Fallunterscheidungen mit if-then-else 51
3.1.11 Kommentare angeben 51
3.2 Operatoren definieren 52
3.2.1 Assoziativität und Bindungsstärke 52
3.2.2 Präfixschreibweise – Operatoren zu Funktionen 53
3.2.3 Infixschreibweise – Funktionen zu Operatoren 54
3.2.4 Eigene Operatoren definieren 54
3.3 Lambda-Notation 55
3.4 Übungsaufgaben 56
4 Rekursion als Entwurfstechnik 57
4.1 Rekursive Fakultätsfunktion 58
4.2 Lineare Rekursion 59
4.3 Kaskadenförmige Rekursion 60
4.4 Verschachtelte Rekursion 61
4.5 Wechselseitige Rekursion 62
4.6 Endständige Rekursion 62
4.7 Übungsaufgaben 62
5 Einfache Datenstrukturen 64
5.1 Listen 65
5.1.1 Zerlegung in Kopf und Rest 66
5.1.2 Rekursive Listenfunktionen 68
5.1.3 Zusammenfassen von Listen 70
5.1.4 Automatische Erzeugung von Listen 71
5.1.5 Automatisches Aufzählen von Elementen 72
5.1.6 Lazy evaluation 74
5.1.6.1 Unendliche Listen 74
5.1.6.2 Das Sieb des Eratosthenes 75
5.1.7 Listen zerlegen 76
5.2 Tupel 77
5.2.1 Beispiel pythagoräisches Tripel 78
5.2.2 Beispiel n-Dameproblem 79
5.3 Zeichenketten 80
5.4 Übungsaufgaben 82
6 Funktionen höherer Ordnung 83
6.1 Mapping 85
6.2 Filtern 86
6.3 Faltung 87
6.3.1 Faltung von rechts mit Startwert 88
6.3.2 Faltung von rechts ohne Startwert 91
6.3.3 Faltung von links mit Startwert 92
6.3.4 Faltung von links ohne Startwert 93
6.3.5 Unterschied zwischen Links- und Rechtsfaltung 93
6.4 Entfaltung 94
6.4.1 Definition von unfold 94
6.4.2 Mapping durch unfold 95
6.5 Zip 96
6.6 Unzip 96
6.7 Funktionskompositionen 97
6.8 Currying 99
6.9 Übungsaufgaben 101
7 Eigene Typen und Typklassen definieren 102
7.1 Typsynonyme mit type 103
7.2 Einfache algebraische Typen mit data und newtype 104
7.2.1 Datentyp Tupel 107
7.2.2 Datentyp Either 107
7.2.3 Datentyp Maybe 108
7.2.4 Datentypen mit mehreren Feldern 109
7.3 Rekursive Algebraische Typen 111
7.4 Automatische Instanzen von Typklassen 112
7.4.1 Typklasse Show 113
7.4.2 Typklasse Read 113
7.4.3 Typklasse Eq 114
7.4.4 Typklasse Ord 114
7.4.5 Typklasse Enum 114
7.4.6 Typklasse Bounded 115
7.5 Eingeschränkte Polymorphie 115
7.6 Manuelles Instanziieren 115
7.7 Projekt: Symbolische Differentiation 118
7.7.1 Operatorbaum 119
7.7.2 Polynome berechnen 120
7.7.3 Ableitungsregeln 120
7.7.4 Automatisches Auswerten 121
7.8 Eigene Klassen definieren 122
7.9 Übungsaufgaben 123
8 Modularisierung und Schnittstellen 124
8.1 Module definieren 125
8.2 Sichtbarkeit von Funktionen 125
8.3 Qualified imports 127
8.4 Projekt: Adressbuch 127
8.4.1 Modul Woerterbuch 127
8.4.2 Modul Adressbuch 128
8.4.3 Modul TestAdressbuch 129
8.5 Übungsaufgaben 130
Teil II Fortgeschrittene Haskell-Konzepte 132
9 Laufzeitanalyse von Algorithmen 133
9.1 Motivation 134
9.2 Landau-Symbole 135
9.2.1 Obere Schranken O 135
9.2.2 Starke obere Schranken o 136
9.2.3 Untere Schranken 136
9.2.4 Starke untere Schranken 137
9.2.5 Asymptotisch gleiches Wachstum 137
9.2.6 Definition über Grenzwerte von Quotientenfolgen 137
9.3 Umgang mit Schranken und Regeln 137
9.4 Übersicht wichtiger Laufzeiten 139
9.5 Best, Worst und Average Case 139
9.6 Analysieren der Laufzeit 139
9.6.1 Fakultätsfunktion 140
9.6.2 Elemente in Listen finden 141
9.6.3 Listen umdrehen 142
9.6.4 Potenzen 143
9.6.5 Minimum einer Liste 145
9.7 Übungsaufgaben 147
10 Arrays, Listen und Stacks 148
10.1 Arrays 149
10.1.1 Statische Arrays 149
10.1.2 Dynamische Arrays 151
10.2 Liste und Stack 152
10.3 Listen sortieren 153
10.3.1 SelectionSort 153
10.3.2 InsertionSort 154
10.3.3 BubbleSort 155
10.3.4 QuickSort 157
10.3.5 MergeSort 159
10.3.6 BucketSort 160
10.3.7 RadixSort 161
10.4 Algorithmen auf Stacks 163
10.4.1 Umgekehrte Polnische Notation 163
10.4.2 Projekt: Klammertest 164
10.5 Übungsaufgaben 166
11 Warteschlangen 167
11.1 Implementierung über Listen 168
11.2 Amortisierte Laufzeitanalyse 169
11.2.1 Bankiermethode 169
11.2.2 Analyse der Warteschlange 170
11.3 Erweiterung um Lazy Evaluation 170
11.4 Angepasste amortisierte Analyse 171
11.5 Beispielanwendung 173
11.6 Übungsaufgaben 173
12 Bäume 174
12.1 Implementierung der Datenstruktur Baum 175
12.2 Balancierte Bäume 176
12.3 Traversierungen 177
12.3.1 Pre-, In- und Postorder 177
12.3.2 Levelorder 178
12.4 Übungsaufgaben 179
13 Wörterbücher 180
13.1 Analyse und Vorüberlegungen 181
13.2 Implementierung 182
13.3 Laufzeitanalyse 183
13.4 Übungsaufgaben 184
14 Prioritätswarteschlangen 186
14.1 Operationen und mögliche Umsetzungen 187
14.2 Realisierung mit einer Liste 187
14.3 Realisierung mit einem Binärbaum 187
14.4 Zwei Bäume verschmelzen 189
14.5 Amortisierte Laufzeitanalyse von merge 190
14.6 Beispielanwendung 191
14.7 Übungsaufgaben 192
15 Random-Access Listen 193
15.1 Realisierung mit einem Suchbaum 194
15.1.1 Preorder versus Inorder bei Binärbäumen 194
15.1.2 Liste vollständiger Binärbäume 195
15.1.3 Verschmelzen mit Greedy-Strategie 195
15.2 Implementierung der grundlegenden Listenfunktionen 197
15.3 Implementierung von elementAn 198
15.4 Beispielanwendung 199
15.5 Übungsaufgaben 200
16 Graphen 201
16.1 Definition und wichtige Begriffe 202
16.2 Abstrakter Datentyp Graph 203
16.2.1 Adjazenzliste und Adjazenzmatrix 203
16.2.2 Implementierung der Adjazenzliste 204
16.3 Algorithmen auf Graphen 205
16.3.1 Traversieren von Graphen 206
16.3.1.1 Tiefensuche im Graphen 207
16.3.1.2 Breitensuche im Graphen 208
16.3.1.3 Implementierung von Tiefen- und Breitensuche 208
16.3.2 Topologisches Sortieren 212
16.4 Übungsaufgaben 215
17 Monaden 216
17.1 Einführung und Beispiele 217
17.1.1 Debug-Ausgaben 217
17.1.1.1 Rückgabewert und Funktionskomposition 217
17.1.1.2 Eigene Eingabetypen definieren 218
17.1.1.3 Identitätsfunktion 218
17.1.2 Zufallszahlen 219
17.2 Monaden sind eine Typklasse 220
17.3 do-Notation 221
17.3.1 Allgemeine Umwandlungsregeln 221
17.3.2 Umwandlungsregeln für if-then-else 222
17.3.3 Beispiel 223
17.4 Vordefinierte Monaden 224
17.4.1 Monade Writer 224
17.4.2 Monade Reader 225
17.4.3 Monade State 227
17.4.4 Monade List 229
17.5 Ein- und Ausgaben 231
17.5.1 Stream-basierte Eingaben 231
17.5.2 Monade IO 232
17.5.2.1 Bildschirmausgaben 233
17.5.2.2 Tastatureingaben 234
17.5.2.3 Eingabepufferung 234
17.5.2.4 Beispiel: Hangman 235
17.5.3 Dateien ein- und auslesen 237
17.6 Übungsaufgaben 238
18 Programme verifizieren und testen 240
18.1 Beweis durch vollständige Induktion 241
18.1.1 Die fünf Peano-Axiome 241
18.1.2 Beweiskonzept 242
18.1.2.1 Gaußsche Summenformel 242
18.1.2.2 Vier- und Fünf-Euro-Münze 243
18.1.2.3 Fakultätsfunktion 243
18.1.3 Vollständige Induktion über Strukturen 244
18.1.3.1 Induktion über Listen 245
18.1.3.2 Induktion über Bäume 246
18.2 QuickCheck 247
18.2.1 Beispiel: Sortieren 248
18.2.2 QuickCheck für eigene Typen verwenden 249
18.2.3 Testdatengeneratoren 249
18.3 Übungsaufgaben 250
19 Berechenbarkeit und Lambda-Kalkül 252
19.1 Der Lambda-Kalkül 253
19.2 Formale Sprachdefinition 253
19.2.1 Bezeichner 253
19.2.2 -Funktion 254
19.2.3 Applikation 254
19.2.4 Reguläre -Ausdrücke 254
19.3 Freie und gebundene Variablen 255
19.4 -Ausdrücke auswerten 255
19.4.1 -Konversion 255
19.4.2 -Reduktion 256
19.5 Boolesche Algebra 257
19.5.1 True und False 257
19.5.2 Negation 258
19.5.3 Konjunktion und Disjunktion 258
19.6 Tupel 258
19.6.1 2-Tupel 259
19.6.2 First und Second 259
19.7 Listen 259
19.7.1 Head – Kopf einer Liste 260
19.7.2 Tail – Rest einer Liste 260
19.7.3 Empty – Test auf eine leere Liste und Nil 260
19.8 Arithmetik 261
19.8.1 Natürliche Zahlen 261
19.8.2 Zero – Der Test auf Null 261
19.8.3 S – Die Nachfolgerfunktion 262
19.8.4 Die Addition 263
19.8.5 Die Multiplikation 264
19.8.6 Die Vorgängerfunktion 264
19.9 Rekursion 265
19.9.1 Alternative zu Funktionsnamen 265
19.9.2 Fixpunktkombinatoren 266
19.10 Projekt: -Interpreter 267
19.10.1 -Ausdrücke repräsentieren 268
19.10.2 Auswerten von -Ausdrücken 268
19.10.3 Freie und gebundene Variablen 270
19.10.4 Wörterbuch für Substitutionen 270
19.10.5 -Parser 272
19.11 Übungsaufgaben 274
Lösungen der Aufgaben 275
Literaturverzeichnis 283
Sachverzeichnis 286