[Anwendungen zur Listenimplementierung] [TOP]
Auf Grund der häufigen Verwendung des Datentyps Liste in funktionalen
Sprachen wird für diesen Datentyp eine eigene Syntax verwendet.
Eine Liste von Elementen hätte die Darstellung [a, b, c ..., z]. Elemente
werden über den Infixoperator (:) vorn an eine Liste angefügt, so
dass sich eine nichtleere Liste durch das Muster (x:xs) darstellen läßt.
Die dadurch definierten Selektoren wie
head, tail und der Verkettungsoperator erlauben bereits die Arbeit auf
dem Datentyp.
01 -- Selektoren 02 03 kopf :: [a] -> a 04 schwanz :: [a] -> [a] 05 06 kopf (x:xs) = x 07 schwanz (x:xs) = xs 08 09 verkette :: [a] -> [a] -> [a] 10 verkette [] l2 = l2 11 verkette l1 l2 = (kopf l1): verkette (schwanz l1) l2 |
Der Verkettungsoperator (im Prelude (++)) wird bereits rekursiv definiert. Erst wenn der rekursive Abstieg vollständig abgeschlossen ist (Terminationsbedingung), wird beim Aufstieg das Anfügen des Kopfes nacheinander ausgeführt. Noch klarer wird der Rekursionsmechanismus beim Umkehren einer Liste.
01 umkehren :: [a] -> [a] -> [a] 02 03 umkehren [] = [] 04 umkehren (x:xs) = umkehren xs ++ [x] |
Die Rekursion wird vollständig ausgeführt, ist normal rekursiv.
Soll der Wert der
Funktion sich aus dem jeweiligen rekursiven Aufruf ermitteln, das
Ergebnis nicht nach "oben" gereicht und dort beim rekursiven Aufstieg
weiter bearbeitet, sondern sofort geliefert werden, verwendet man die sogenannte Akkumulatortechnik.
Man spricht in diesem Fall von Endrekursion. Ein gängiges Beispiel ist das Berechnen der Länge
einer Liste.
01 -- rekursiv 02 03 laenge [] = 0 04 laenge (x:xs) = 1 + laenge xs 05 06 -- endrekursiv 07 08 laenge1 [] = 0 09 laenge1 xs = hilfslaenge xs 0 10 where hilfslaenge [] a = a 11 hilfslaenge (x:xs) a = hilfslaenge xs (a+1) |
Haskell stellt ebenfalls die Möglichkeit bereit, unendliche Listen zu erzeugen. Dabei werden Muster
verwendet, die im praktischen Bereich Bedeutung haben.
[1..8] liefert [1,2,3,4,5,6,7,8] [1..] erzeugt die unendliche Liste aller ganzen Zahlen ab 1 und [1,3..] die aller ungeraden Zahlen
Mit dieser Reglementierung ist es möglich Beschreibungen (list comprehension) für beliebig große Listen zu liefern. Die Liste der geraden Zahlen stellt sich danach wie folgt dar.
01 gerade = [x | x <- [1..], mod x 2 == 0]
|
Die Nähe zur Mengenschreibweise ist gewollt. Der Ergebnisterm besteht aus den x, die aus der unendlichen Menge
ganzer Zahlen ([1..]) über die boolsche Bedingung (mod x 2 == 0) herausgefiltert werden. Dabei ist in diesem
Beispiel (x <- [1..]) der Generator und (mod x 2 == 0) die Filterbedingung.
Ein sehr bekanntes und übersichtliches Beispiel zur Anwendung von Listenbeschreibungen stellt das Sieb des
Erastosthenes dar. Dabei werden aus einer Liste von ganzen Zahlen beginnend bei der Zahl 2 alle Vielfachen der
ersten Zahl gestrichen. Es entsteht eine gefilterte Liste, in der die geraden Zahlen gestrichen sind. Wenn es
höhere nicht gestrichene Zahlen gibt, werden deren Vielfache gewählt und ebenso gestrichen. Übrig bleiben nach diesem Verfahren
nur die Primzahlen.
Eine Anwendung der elementaren Listenfunktion take (siehe oben) liefert die gewünschte Anzahl.
01 primzahlen = sieb [2..] 02 03 sieb (k:xs) = k :sieb [n | n <-xs, mod n k /= 0] 04 05 ergebnis = take 100 primzahlen |