- Titel: Einführung in die Funktionale Programmierung
- Autor: David Sabel
- Organisation: UNI FRANKFURT
- Seitenzahl: 216
Inhalt
- Einleitung
- Was sind funktionale Programmiersprachen?
- Warum Funktionale Programmierung?
- Klassifizierung funktionaler Programmiersprachen
- Inhalte und Ziele
- Literatur
- Funktionale Kernsprachen
- Der Lambda-Kalkül
- Normalordnungsreduktion
- Anwendungsordnung
- Verzögerte Auswertung
- Programmieren mit Let-Ausdrücken in Haskell
- Lokale Funktionsdefinitionen mit let
- Pattern-Matching mit let
- Memoization
- where-Ausdrücke
- Gleichheit von Programmen
- Kernsprachen von Haskell
- Die Kernsprache KFPT
- Syntax von KFPT
- Freie und gebundene Variablen in KFPT
- Operationale Semantik für KFPT
- Dynamische Typisierung
- Suche nach dem Normalordnungsredex mit einem Markierungsalgorithmus
- Darstellung von Termen als Termgraphen
- Eigenschaften der Normalordnungsreduktion
- Die Kernsprache KFPTS
- Syntax
- Auswertung von KFPTS-Ausdrücken
- Erweiterung um seq
- KFPTSP
- Zusammenfassung
- Quellennachweis und weiterführende Literatur
- Haskell
- Arithmetische Operatoren und Zahlen
- Darstellung von Zahlen in KFPTSP+seq
- Algebraische Datentypen in Haskell
- Aufzählungstypen
- Produkttypen
- Record-Syntax
- Parametrisierte Datentypen
- Rekursive Datenstrukturen
- Listenverarbeitung in Haskell
- Listen von Zahlen
- Strings
- Standard-Listenfunktionen
- Append
- Zugriff auf ein Element
- Map
- Filter
- Length
- Reverse
- Repeat und Replicate
- Take und Drop
- Zip und Unzip
- Die Fold-Funktionen
- Scanl und Scanr
- Partition und Quicksort
- Listen als Ströme
- Lookup
- Mengenoperation
- List Comprehensions
- Rekursive Datenstrukturen
- Syntaxbäume
- Typdefinitionen
- Haskells hierarchisches Modulsystem
- Moduldefinitionen in Haskell
- Modulexport
- Modulimport
- Hierarchische Modulstruktur
- Haskells Typklassensystem
- Vererbung und Mehrfachvererbung
- Klassenbeschränkungen bei Instanzen
- Die Read- und Show-Klassen
- Die Klassen Num und Enum
- Konstruktorklassen
- Übersicht über die vordefinierten Typklassen
- Auflösung der Überladung
- Erweiterung von Typklassen
- Quellennachweise und weiterführende Literatur
- Typisierung
- Motivation
- Typen
- Polymorphe Typisierung für KFPTSP+seq-Ausdrücke
- Typisierung von nicht-rekursiven Superkombinatoren
- Typisierung rekursiver Superkombinatoren
- Das iterative Typisierungsverfahren
- Beispiele für die iterative Typisierung und Eigenschaften des Verfahrens
- Das iterative Verfahren ist allgemeiner als Haskell
- Das iterative Verfahren benötigt mehrere Iterationen
- Das iterative Verfahren muss nicht terminieren
- Erzwingen der Terminierung
- Das Milner-Typisierungsverfahren
- Haskells Monomorphism Restriction
- Zusammenfassung und Quellennachweis
- IO in Haskell und Monadisches Programmieren
- Monadisches Programmieren
- Die Monadischen Gesetze
- Weitere Monaden
- Die Listen-Monade
- Die StateTransformer-Monade
- Ein- und Ausgabe
- Primitive I/O-Operationen
- Komposition von I/O-Aktionen
- Implementierung der IO-Monade
- Monadische Gesetze und die IO-Monade
- Verzögern innerhalb der IO-Monade
- Speicherzellen
- Kontrollstrukturen — Schleifen
- Nützliche Monaden-Funktionen
- Monad-Transformer
- Quellennachweis
- Literatur
- Simulation von Turingmaschinen in Haskell
Vorschau
Einführung in die Funktionale Programmierung
Wintersemester 2010/11
Dr. David Sabel Institut für Informatik Fachbereich Informatik und Mathematik Goethe-Universität Frankfurt am Main Postfach 11 19 32 D-60054 Frankfurt am Main Email: sabel@ki.informatik.uni-frankfurt.de
Stand: 28. März 2011
Inhaltsverzeichnis
1
Einleitung 1.1 Was sind funktionale Programmiersprachen? . . . 1.2 Warum Funktionale Programmierung? . . . . . . . 1.3 Klassifizierung funktionaler Programmiersprachen 1.4 Inhalte und iele . . . . . . . . . . . . . . . . . . . . 1.5 Literatur . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
2 2 3 6 10 10 13 14 19 21 23 27 27 28 28 30 31 32 33 33 36 38 41 42 45 48 49 49
Funktionale Kernsprachen 2.1 Der Lambda-Kalkül . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Normalordnungsreduktion . . . . . . . . . . . . . . . . 2.1.2 Anwendungsordnung . . . . . . . . . . . . . . . . . . . 2.1.3 Verzögerte Auswertung . . . . . . . . . . . . . . . . . . 2.1.4 Programmieren mit Let-Ausdrücken in Haskell . . . . 2.1.4.1 Lokale Funktionsdefinitionen mit let . . . . 2.1.4.2 Pattern-Matching mit let . . . . . . . . . . . 2.1.4.3 Memoization . . . . . . . . . . . . . . . . . . . 2.1.4.4 where-Ausdrücke . . . . . . . . . . . . . . . . 2.1.5 Gleichheit von Programmen . . . . . . . . . . . . . . . 2.1.6 Kernsprachen von Haskell . . . . . . . . . . . . . . . . 2.2 Die Kernsprache KFPT . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Syntax von KFPT . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Freie und gebundene Variablen in KFPT . . . . . . . . 2.2.3 Operationale Semantik für KFPT . . . . . . . . . . . . . 2.2.4 Dynamische Typisierung . . . . . . . . . . . . . . . . . 2.2.5 Suche nach dem Normalordnungsredex mit einem Markierungsalgorithmus . . . . . . . . . . . . . . . . . 2.2.6 Darstellung von Termen als Termgraphen . . . . . . . 2.2.7 Eigenschaften der Normalordnungsreduktion . . . . . 2.3 Die Kernsprache KFPTS . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D. Sabel, Skript EFP, WS 2010/11
Stand: 28. März 2011
Inhaltsverzeichnis
2.4 2.5 2.6 2.7 3
2.3.2 Auswertung von KFPTS-Ausdrücken . . Erweiterung um seq . . . . . . . . . . . . . . . . KFPTSP: Polymorphe Typen . . . . . . . . . . . . usammenfassung . . . . . . . . . . . . . . . . . Quellennachweis und weiterführende Literatur
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
50 51 54 57 57 59 60 61 63 63 65 67 69 70 71 71 73 73 73 74 75 75 76 76 77 77 79 80 82 83 84 86 86 88 91 98 102
Haskell 3.1 Arithmetische Operatoren und ahlen . . . . . 3.1.1 Darstellung von ahlen in KFPTSP+seq 3.2 Algebraische Datentypen in Haskell . . . . . . . 3.2.1 Aufzählungstypen . . . . . . . . . . . . . 3.2.2 Produkttypen . . . . . . . . . . . . . . . . 3.2.2.1 Record-Syntax . . . . . . . . . . 3.2.3 Parametrisierte Datentypen . . . . . . . . 3.2.4 Rekursive Datenstrukturen . . . . . . . . 3.3 Listenverarbeitung in Haskell . . . . . . . . . . . 3.3.1 Listen von ahlen . . . . . . . . . . . . . 3.3.2 Strings . . . . . . . . . . . . . . . . . . . . 3.3.3 Standard-Listenfunktionen . . . . . . . . 3.3.3.1 Append . . . . . . . . . . . . . . 3.3.3.2 ugriff auf ein Element . . . . . 3.3.3.3 Map . . . . . . . . . . . . . . . . 3.3.3.4 Filter . . . . . . . . . . . . . . . . 3.3.3.5 Length . . . . . . . . . . . . . . 3.3.3.6 Reverse . . . . . . . . . . . . . . 3.3.3.7 Repeat und Replicate . . . . . . 3.3.3.8 Take und Drop . . . . . . . . . . 3.3.3.9 ip und Unzip . . . . . . . . . . 3.3.3.10 Die Fold-Funktionen . . . . . . 3.3.3.11 Scanl und Scanr . . . . . . . . . 3.3.3.12 Partition und Quicksort . . . . 3.3.3.13 Listen als Ströme . . . . . . . . 3.3.3.14 Lookup . . . . . . . . . . . . . . 3.3.3.15 Mengenoperation . . . . . . . . 3.3.4 List Comprehensions . . . . . . . . . . . . 3.4 Rekursive Datenstrukturen: Bäume . . . . . . . 3.4.1 Syntaxbäume . . . . . . . . . . . . . . . . 3.5 Typdefinitionen: data, type, newtype . . . . . .