Grundlagen und Methoden funktionaler Programmierung

24. June 2011 Informatik
  • Titel: Grundlagen und Methoden funktionaler Programmierung
  • Organisation: UNI DORTMUND
  • Seitenzahl: 122

Skript herunterladen (PDF)

Inhalt

  • Funktionales Programmieren und ML
  • Programmierparadigmen
  • Literatur
  • Kontextfreie Grammatik von ML
  • Typen, Ausdrücke und Definitionen
  • Funktionen in der Mathematik
  • Typen
  • Primitive Typen
  • Zusammengesetzte Typen
  • Definitionen
  • Werte
  • Funktionen
  • Fallunterscheidungen
  • Konditionale
  • Argumentmuster
  • Rekursive Definitionen
  • Scopes und lokale Definitionen
  • Polymorphie
  • Overloading
  • Funktionen höherer Ordnung
  • -Abstraktion
  • Eifrige und verzögerte Auswertung
  • Korrektheitsbeweise
  • Vollständige Induktion über N
  • Fixpunktinduktion
  • Listen
  • Listenoperationen
  • Keller und Schlangen
  • Listenerzeugung
  • Listensortierung
  • Sortieren durch Einfügen (insertion sort)
  • Sortieren durch Filtern (quicksort)
  • Sortieren durch Mischen (mergesort)
  • Induktion über Listen
  • Transformation und Verifikation
  • Akkumulatoren
  • Keller
  • Continuations
  • Verifikation iterativer Programme
  • Funktionen als Datenstrukturen
  • Adjazenzmatrizen
  • Kürzeste Wege
  • Adjazenzlisten
  • Minimale Gerüste von Graphen
  • Funktionen Matrizen
  • Ausgabe von Matrizen
  • Matrizenarithmetik
  • Transitiver Abschluß
  • Konstruktorbasierte Datentypen
  • Symbolisches Rechnen
  • Konstruktoren versus Ausnahmen
  • Abstrakte Datentypen
  • Binäre Bäume
  • Traversierungen binärer Bäume
  • Heaps
  • Heapsort
  • Der Huffman-Algorithmus
  • Text einlesen
  • Codebaum erzeugen
  • Codieren und decodieren
  • Bäume mit beliebigem Ausgrad
  • Bäume zeichnen mit PostScript
  • Ein Parser
  • Knotenkoordinaten berechnen
  • Knoten und Kanten zeichnen
  • Dynamische Objekte
  • Statische und dynamische Bindung
  • Die Türme von Hanoi
  • Verkettete Datenstrukturen
  • Bäume und Graphen
  • Modularisierung
  • Strukturen
  • Signaturen
  • Funktoren
  • Objektorientierte Programmierung
  • Regale bauen
  • Permutationen
  • Konstruktorbasierte Datentypen
  • Scanning und Parsing
  • Ausnahmen und dynamische Variablen
  • Modularisierung
  • Compiling
  • Structures in concert
  • Ströme und verzögerte Auswertung
  • Logisches Programmieren
  • Auswerten versus Lösen
  • Rekursive Wertdefinitionen
  • Anhang
  • drawTree
  • buildShelves
  • compFitness

Vorschau

Grundlagen und Methoden funktionaler Programmierung

Sommersemester 1999

Peter Padawitz http://padawitz.de University of Dortmund, Germany 9. Dezember 2009

2

INHALTSVER EICHNIS

Inhaltsverzeichnis

1 Funktionales Programmieren und ML 1.1 1.2 1.3 Programmierparadigmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kontextfreie Grammatik von ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 6 8 8 9 9

2 Typen, Ausdrücke und Definitionen 2.1 2.2 Funktionen in der Mathematik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 2.2.2 2.3 Primitive Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

usammengesetzte Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1 2.3.2 Werte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4

Fallunterscheidungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 2.4.2 Konditionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Argumentmuster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 2.6 2.7 2.8 2.9

Rekursive Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Scopes und lokale Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Polymorphie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Funktionen höherer Ordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.10 λ-Abstraktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.11 Eifrige und verzögerte Auswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Korrektheitsbeweise 3.1 3.2 Vollständige Induktion über N 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Fixpunktinduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 23

4 Listen 4.1 4.2 4.3 4.4

Listenoperationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Keller und Schlangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Listenerzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Listensortierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4.1 Sortieren durch Einfügen (insertion sort) . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

INHALTSVER EICHNIS

4.4.2 4.4.3 4.5

Sortieren durch Filtern (quicksort) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Sortieren durch Mischen (mergesort) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Induktion über Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 30

5 Transformation und Verifikation 5.1 5.2 5.3 5.4

Akkumulatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Keller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Verifikation iterativer Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 35

6 Funktionen als Datenstrukturen 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8

Adjazenzmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Kürzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Adjazenzlisten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Minimale Gerüste von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Funktionen ; Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Ausgabe von Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Matrizenarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Transitiver Abschluß . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 51

7 Konstruktorbasierte Datentypen 7.1 7.2 7.3

Symbolisches Rechnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Konstruktoren versus Ausnahmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Abstrakte Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 57

8 Binäre Bäume 8.1 8.2

Traversierungen binärer Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.2.1 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

8.3

Der Huffman-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 8.3.1 8.3.2 8.3.3 Text einlesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Codebaum erzeugen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Codieren und decodieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 65

9 Bäume mit beliebigem Ausgrad 9.1

Bäume zeichnen mit PostScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 9.1.1 Ein Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67