Suchen und Finden
Service
Haskell-Intensivkurs - Ein kompakter Einstieg in die funktionale Programmierung
Marco Block, Adrian Neumann
Verlag Springer-Verlag, 2011
ISBN 9783642047183 , 300 Seiten
Format PDF
Kopierschutz Wasserzeichen
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