Verarbeitung von Listen

Die Datenstruktur in der funktionalen Programmierung ist die Liste. Sie ist auch der Namensgeber für die funktionale Programmiersprache LISP ("LISt Processing"). Funktionale Programme bestehen gerne sowohl im Kleinen aus Listen, die in neue Listen transformiert (Listing 5) werden, als auch im Großen aus Operationen über Listen (Abbildung 5), die komponiert werden.

myMap :: (t -> a) -> [t] -> [a]
myMap f [] = []
myMap f (x:xs)= f x: myMap f xs

Die Funktion "myMap", die die Funktionalität der built-in Funktion "map" anbietet, wendet sukzessive die Funktion f auf die Elemente der Liste an und gibt eine neue Liste mit den transformierten Elementen zurück. Aber nun zu den Details.
Es gehört zum guten Stil in Haskell, die Funktionsdeklaration einer Funktion anzugegen. Die erste Zeile "myMap :: (t -> a) -> [t] -> [a]" beschreibt die Funktion, die zwei Argumente erwartet. Das erste Argument ist eine Funktion von "t -> a " und das Zweite eine Liste über "[t]". Als Ergebnis gibt sie eine neue Liste "[a]" über "a" zurück. "t" und "a" sind sogenannte Typeparameter.

Nach der Deklaration folgt in den nächsten zwei Zeilen die Definition der Funktion. Wieder unterscheidet "myMap", ob das Argument die leere Liste "[]" ist, oder die Liste aus mindestens einem Element "(x:xs)". Dieser Ausdruck beschreibt die Liste aus dem ersten Element "x" und dem Rest der List "xs". "myMap" bildet die leere Liste auf die leere Liste ab: "myMap f [] = []".

Die tatsächliche Arbeit geschieht erst in dem Ausdruck "myMap f (x:xs)= f x: myMap f xs". Auf der rechten Seite der Gleichung wird nun f auf jedes Element x angewendet "f x " und zu eine neuen Liste verküpft ":" und dies, bis die ganze Liste abgearbeitet ist. Tritt dieser Fall ein, so sorgt "myMap f [] = []" dafür,dass die Rekursion terminiert.

Um ein tieferes Verständnis der rekursiven Algorithmen zu erlangen, ist es am hilfreichsten, ein einfaches Beispiel mit Blatt und Stift durchzuspielen.

Abbildung 5: Funktionskomposition in Haskell.

Bedarfsauswertung

Bei der Bedarfsauswertung (Lazy Evaluation) werden Ausdrücke erst dann berechnet, wenn sie tatsächlich benötigt werden. Dies beherrschen mehrere funktionale Programmiersprachen wie Miranda oder Haskell. Durch Bedarfsauswertung lässt sich die Strategie zur Berechnung einer Liste von deren Nutzung elegant trennen. Durch den Algorithmus "Sieb des Eratosthenes" in Listing 6 wird die unendliche Folge aller Primzahlen definiert.

primes::[Int]
primes = sieve[2..]
sieve (x:xs) = x: sieve[ y | y <- xs, y `mod` x > 0 ]

Ist die Funktion definiert, lassen sich einfach die ersten 200 Primzahlen oder die 10000-te Primzahl anfordern. Die Built-In-Funktion "take :: Int -> [a] -> [a]" gibt aus einer (unendlichen) Liste die maximal "Int" ersten Elemente zurück. "!!" ist der Indexoperator in Haskell.

Abbildung 6: Das Sieb des Eratosthenes ermittelt Primzahlen.