Haskell-Intensivkurs - Ein kompakter Einstieg in die funktionale Programmierung

1 Motivation und Einführung

1.1 Funktionale Programmierung

1.1.1 Motivation und Anwendung

1.1.2 Warum gerade Haskell?

1.2 Grundbegriffe und Prinzipien der Programmentwicklung

1.3 Installation und Verwendung von Haskell

1.3.1 Installation der aktuellen Version

1.3.2 Die ersten Schritte in Hugs

1.3.3 Arbeiten auf der Konsole

1.3.4 Die Entwicklungsumgebung winhugs

1.3.5 Erstellung und Verwendung von Skripten

1.4 Haskell ist mehr als ein Taschenrechner

1.5 Vordefinierte Funktionen der Prelude

Teil I Haskell-Grundlagen

2 Einfache Datentypen

2.1 Wahrheitswerte

2.1.1 Negation

2.1.2 Konjunktion

2.1.3 Disjunktion

2.1.4 Exklusiv-Oder

2.1.5 Boolesche Algebra

2.1.6 Boolesche Gesetze

2.2 Zahlentypen

2.2.1 Datentyp Int

2.2.2 Datentyp Integer

2.2.3 Datentypen Float und Double

2.3 Zeichen und Symbole

2.4 Übungsaufgaben

3 Funktionen und Operatoren

3.1 Funktionen definieren

3.1.1 Parameterübergabe

3.1.2 Reservierte Schlüsselwörter

3.1.3 Wildcards

3.1.4 Signaturen und Typsicherheit

3.1.5 Pattern matching

3.1.6 Pattern matching mit case

3.1.7 Lokale Definitionen mit where

3.1.8 Lokale Definitionen mit let-in

3.1.9 Fallunterscheidungen mit Guards

3.1.10 Fallunterscheidungen mit if-then-else

3.1.11 Kommentare angeben

3.2 Operatoren definieren

3.2.1 Assoziativität und Bindungsstärke

3.2.2 Präfixschreibweise – Operatoren zu Funktionen

3.2.3 Infixschreibweise – Funktionen zu Operatoren

3.2.4 Eigene Operatoren definieren

3.3 Lambda-Notation

3.4 Übungsaufgaben

4 Rekursion als Entwurfstechnik

4.1 Rekursive Fakultätsfunktion

4.2 Lineare Rekursion

4.3 Kaskadenförmige Rekursion

4.4 Verschachtelte Rekursion

4.5 Wechselseitige Rekursion

4.6 Endständige Rekursion

4.7 Übungsaufgaben

5 Einfache Datenstrukturen

5.1 Listen

5.1.1 Zerlegung in Kopf und Rest

5.1.2 Rekursive Listenfunktionen

5.1.3 Zusammenfassen von Listen

5.1.4 Automatische Erzeugung von Listen

5.1.5 Automatisches Aufzählen von Elementen

5.1.6 Lazy evaluation

5.1.6.1 Unendliche Listen

5.1.6.2 Das Sieb des Eratosthenes

5.1.7 Listen zerlegen

5.2 Tupel

5.2.1 Beispiel pythagoräisches Tripel

5.2.2 Beispiel n-Dameproblem

5.3 Zeichenketten

5.4 Übungsaufgaben

6 Funktionen höherer Ordnung

6.1 Mapping

6.2 Filtern

6.3 Faltung

6.3.1 Faltung von rechts mit Startwert

6.3.2 Faltung von rechts ohne Startwert

6.3.3 Faltung von links mit Startwert

6.3.4 Faltung von links ohne Startwert

6.3.5 Unterschied zwischen Links- und Rechtsfaltung

6.4 Entfaltung

6.4.1 Definition von unfold

6.4.2 Mapping durch unfold

6.5 Zip

6.6 Unzip

6.7 Funktionskompositionen

6.8 Currying

6.9 Übungsaufgaben

7 Eigene Typen und Typklassen definieren

7.1 Typsynonyme mit type

7.2 Einfache algebraische Typen mit data und newtype

7.2.1 Datentyp Tupel

7.2.2 Datentyp Either

7.2.3 Datentyp Maybe

7.2.4 Datentypen mit mehreren Feldern

7.3 Rekursive Algebraische Typen

7.4 Automatische Instanzen von Typklassen

7.4.1 Typklasse Show

7.4.2 Typklasse Read

7.4.3 Typklasse Eq

7.4.4 Typklasse Ord

7.4.5 Typklasse Enum

7.4.6 Typklasse Bounded

7.5 Eingeschränkte Polymorphie

7.6 Manuelles Instanziieren

7.7 Projekt: Symbolische Differentiation

7.7.1 Operatorbaum

7.7.2 Polynome berechnen

7.7.3 Ableitungsregeln

7.7.4 Automatisches Auswerten

7.8 Eigene Klassen definieren

7.9 Übungsaufgaben

8 Modularisierung und Schnittstellen

8.1 Module definieren

8.2 Sichtbarkeit von Funktionen

8.3 Qualified imports

8.4 Projekt: Adressbuch

8.4.1 Modul Woerterbuch

8.4.2 Modul Adressbuch

8.4.3 Modul TestAdressbuch

8.5 Übungsaufgaben

Teil II Fortgeschrittene Haskell-Konzepte

9 Laufzeitanalyse von Algorithmen

9.1 Motivation

9.2 Landau-Symbole

9.2.1 Obere Schranken O

9.2.2 Starke obere Schranken o

9.2.3 Untere Schranken

9.2.4 Starke untere Schranken

9.2.5 Asymptotisch gleiches Wachstum

9.2.6 Definition über Grenzwerte von Quotientenfolgen

9.3 Umgang mit Schranken und Regeln

9.4 Übersicht wichtiger Laufzeiten

9.5 Best, Worst und Average Case

9.6 Analysieren der Laufzeit

9.6.1 Fakultätsfunktion

9.6.2 Elemente in Listen finden

9.6.3 Listen umdrehen

9.6.4 Potenzen

9.6.5 Minimum einer Liste

9.7 Übungsaufgaben

10 Arrays, Listen und Stacks

10.1 Arrays

10.1.1 Statische Arrays

10.1.2 Dynamische Arrays

10.2 Liste und Stack

10.3 Listen sortieren

10.3.1 SelectionSort

10.3.2 InsertionSort

10.3.3 BubbleSort

10.3.4 QuickSort

10.3.5 MergeSort

10.3.6 BucketSort

10.3.7 RadixSort

10.4 Algorithmen auf Stacks

10.4.1 Umgekehrte Polnische Notation

10.4.2 Projekt: Klammertest

10.5 Übungsaufgaben

11 Warteschlangen

11.1 Implementierung über Listen

11.2 Amortisierte Laufzeitanalyse

11.2.1 Bankiermethode

11.2.2 Analyse der Warteschlange

11.3 Erweiterung um Lazy Evaluation

11.4 Angepasste amortisierte Analyse

11.5 Beispielanwendung

11.6 Übungsaufgaben

12 Bäume

12.1 Implementierung der Datenstruktur Baum

12.2 Balancierte Bäume

12.3 Traversierungen

12.3.1 Pre-, In- und Postorder

12.3.2 Levelorder

12.4 Übungsaufgaben

13 Wörterbücher

13.1 Analyse und Vorüberlegungen

13.2 Implementierung

13.3 Laufzeitanalyse

13.4 Übungsaufgaben

14 Prioritätswarteschlangen

14.1 Operationen und mögliche Umsetzungen

14.2 Realisierung mit einer Liste

14.3 Realisierung mit einem Binärbaum

14.4 Zwei Bäume verschmelzen

14.5 Amortisierte Laufzeitanalyse von merge

14.6 Beispielanwendung

14.7 Übungsaufgaben

15 Random-Access Listen

15.1 Realisierung mit einem Suchbaum

15.1.1 Preorder versus Inorder bei Binärbäumen

15.1.2 Liste vollständiger Binärbäume

15.1.3 Verschmelzen mit Greedy-Strategie

15.2 Implementierung der grundlegenden Listenfunktionen

15.3 Implementierung von elementAn

15.4 Beispielanwendung

15.5 Übungsaufgaben

16 Graphen

16.1 Definition und wichtige Begriffe

16.2 Abstrakter Datentyp Graph

16.2.1 Adjazenzliste und Adjazenzmatrix

16.2.2 Implementierung der Adjazenzliste

16.3 Algorithmen auf Graphen

16.3.1 Traversieren von Graphen

16.3.1.1 Tiefensuche im Graphen

16.3.1.2 Breitensuche im Graphen

16.3.1.3 Implementierung von Tiefen- und Breitensuche

16.3.2 Topologisches Sortieren

16.4 Übungsaufgaben

17 Monaden

17.1 Einführung und Beispiele

17.1.1 Debug-Ausgaben

17.1.1.1 Rückgabewert und Funktionskomposition

17.1.1.2 Eigene Eingabetypen definieren

17.1.1.3 Identitätsfunktion

17.1.2 Zufallszahlen

17.2 Monaden sind eine Typklasse

17.3 do-Notation

17.3.1 Allgemeine Umwandlungsregeln

17.3.2 Umwandlungsregeln für if-then-else

17.3.3 Beispiel

17.4 Vordefinierte Monaden

17.4.1 Monade Writer

17.4.2 Monade Reader

17.4.3 Monade State

17.4.4 Monade List

17.5 Ein- und Ausgaben

17.5.1 Stream-basierte Eingaben

17.5.2 Monade IO

17.5.2.1 Bildschirmausgaben

17.5.2.2 Tastatureingaben

17.5.2.3 Eingabepufferung

17.5.2.4 Beispiel: Hangman

17.5.3 Dateien ein- und auslesen

17.6 Übungsaufgaben

18 Programme verifizieren und testen

18.1 Beweis durch vollständige Induktion

18.1.1 Die fünf Peano-Axiome

18.1.2 Beweiskonzept

18.1.2.1 Gaußsche Summenformel

18.1.2.2 Vier- und Fünf-Euro-Münze

18.1.2.3 Fakultätsfunktion

18.1.3 Vollständige Induktion über Strukturen

18.1.3.1 Induktion über Listen

18.1.3.2 Induktion über Bäume

18.2 QuickCheck

18.2.1 Beispiel: Sortieren

18.2.2 QuickCheck für eigene Typen verwenden

18.2.3 Testdatengeneratoren

18.3 Übungsaufgaben

19 Berechenbarkeit und Lambda-Kalkül

19.1 Der Lambda-Kalkül

19.2 Formale Sprachdefinition

19.2.1 Bezeichner

19.2.2 -Funktion

19.2.3 Applikation

19.2.4 Reguläre -Ausdrücke

19.3 Freie und gebundene Variablen

19.4 -Ausdrücke auswerten

19.4.1 -Konversion

19.4.2 -Reduktion

19.5 Boolesche Algebra

19.5.1 True und False

19.5.2 Negation

19.5.3 Konjunktion und Disjunktion

19.6 Tupel

19.6.1 2-Tupel

19.6.2 First und Second

19.7 Listen

19.7.1 Head – Kopf einer Liste

19.7.2 Tail – Rest einer Liste

19.7.3 Empty – Test auf eine leere Liste und Nil

19.8 Arithmetik

19.8.1 Natürliche Zahlen

19.8.2 Zero – Der Test auf Null

19.8.3 S – Die Nachfolgerfunktion

19.8.4 Die Addition

19.8.5 Die Multiplikation

19.8.6 Die Vorgängerfunktion

19.9 Rekursion

19.9.1 Alternative zu Funktionsnamen

19.9.2 Fixpunktkombinatoren

19.10 Projekt: -Interpreter

19.10.1 -Ausdrücke repräsentieren

19.10.2 Auswerten von -Ausdrücken

19.10.3 Freie und gebundene Variablen

19.10.4 Wörterbuch für Substitutionen

19.10.5 -Parser

19.11 Übungsaufgaben

Lösungen der Aufgaben

Literaturverzeichnis

Sachverzeichnis