Praxis der Funktionalen Programmierung (27. 10.)

Wiederholung Listen

Wir betrachten nochmal das Programm für Append (++) und beweisen eine Eigenschaft durch Induktion. Das gleiche für das Umdrehen von Listen (reverse). Natürlich wünschen wir uns, daß diese Beweise werden. Wieweit geht das? Es ist Equational Reasoning, siehe Vorlesung Term-Ersetzung (Dr. Hartwig).

Eine typische Aktion auf Listen ist das Sortieren. Wir können Quicksort sehr direkt hinschreiben. Es hat aber die bekannten Nachteile, falls wir ungünstige Pivot-Elemente benutzen, und die Laufzeit leidet zusätzlich durch die naive Implementierung.

Sicherer ist Mergesort. Wir schreiben zuerst die top-down, dann die bottom-up-Variante, und verbessern diese schließlich (Hausaufgabe).

best viewed with any browser

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de