List comprehension

Viele Programmiersprachen bieten List Comprehension als "syntactic sugar" für die Funktionen "map" und "filter" an. Der List-Comprehension-Ausdruck "[ f(x) | x <-xs, pred(x) ]" erzeugt eine Liste durch folgende Vorschrift: Wende "f(x)" auf alle Elemente "x" aus "xs" an, die die Filterfunktion "pred(x)" erfüllen.

Die Beispiele zu "map" und "filter" aus Abbildung 2 lassen sich einfach in List Comprehension ausdrücken oder auch verknüpfen, wie Abbildung 3 zeigt.

Abbildung 3: List Comprehension mit Haskell.

Mit List Comprehension lässt sich der Sortieralgorithmus Quicksort sehr elegant und kompakt zugleich implementieren (Listing 2).

qsort []     = []
qsort (p:xs) = qsort [x| x <-xs, x < p ]  ++ [p] ++  qsort [x| x <-xs, x >= p 

Diese Haskell-Funktion benötigt ein paar Erläuterungen. Die zwei Zeilen definieren die Funktion "qsort". Hier muß zwischen der leeren Liste "[]" und der Liste mit mindestens einem Element "(p:xs)" unterschieden werden. Die leere Liste sortiert ergibt naheliegenderweise die leere Liste ("qsort [] = []").

Die eigentliche Sortierung findet in "qsort (p:xs) = qsort [x| x <-xs, x < p ] ++ [p] ++ qsort [x| x <-xs, x >= p ] " statt. Die rekursive Strategie ist schnell erklärt: Nimm das erste Elemente p aus der Eingabeliste ("(p:xs)"), bilde die Liste der Elemente kleiner als p ("[x| x <-xs, x < p ])" und größer oder gleich p ("[x| x &llt;-xs, x >= p ]") und verbinde sie mit der Liste mit dem Element p (" ++ [p] ++ "). Wende Quicksort rekursiv auf die resultierenden Listen an, die mehr als ein Element besitzen ("qsort [x| x <-xs, x < p ]"). Abbildung 4 zeigt Quicksort in Aktion.

Abbildung 4: Quicksort-Algorithmus in Aktion.

Reine Funktionen

Haskell kennt nur reine Funktionen. In dem Buch Real World Haskell von Bryan O'Sullivan, Don Stewart und John Goerzen findet sich eine schöne Gegenüberstellung von reinen und unreinen Funktionen.

Die Vorteile von reinen Funktionen sind offensichtlich. Der Programmverhalten wird deutlich transparenter, sodass

• Korrektheitsbeweise einfacher durchzuführen sind
• Refaktoring und Testen einfacher möglich ist
• Zwischenergebnisse von Funktionsaufrufen gespeichert werden können (Referenzielle Transparenz)
• die Ausführungsreihenfolge der Funktionen umgeordnet oder parallelisiert werden kann