Fachkonzept: Die Listenfunktionen filter und fold
Die Listenfunktion filter
Mit der Funktion filter können wir Elemente einer Liste
auf bestimmte Bedingungen selektieren.
filter bekommt eine Funktion und eine Liste übergeben.
Die übergebene Funktion muss einen Wahrheitswert zurückgeben und wird auf jedes Element der Liste angewandt.
Alle Elemente, für die die Funktion
#t zurückgibt, werden zu einer neuen Liste zusammengefügt und zurückgegeben.
Ein filter-Ausdrucks in Racket besteht aus:
-
Dem Operator
filter - Einer Funktion als ersten Operanden
- Einer Liste als zweiten Operanden.
(filter funktion liste)Da die übergebene Funktion auf alle Elemente der übergebenen Liste angewendet wird, gilt die folgende Einschränkung:
Wenn die Liste Elemente vom Typ
%a beinhaltet, muss die Funktion von der Signatur %a -> boolean sein.
Für die Funktion
filter ergibt sich somit die Signatur:
((%a -> boolean) (list-of %a) -> (list-of %a)).
Zusatzinfo: Prädikate
Funktionen, deren Signatur vom Typ %a ... %n -> boolean sind, nennt man auch
Prädikate. Prädikate stellen Funktionen dar, die in Abhängigkeit der Übergabedaten zu
einem Wahrheitswert auswerten. Ein Prädikat überprüft also immer, ob eine bestimmte Bedingung erfüllt ist.
Beispiele:
Der Ausdruck
(filter natural? (list 42 #t 3.4 17 "keinNatural"))entspricht:
((any -> boolean) (list-of any) -> (list-of natural))
Der Ausdruck
(filter (lambda (x) (<= 18 x)) (list 16 17 18 14 18 17 19))entspricht:
((number -> boolean) (list-of natural) -> (list-of natural))
Die Listenfunktion fold
Mit der Funktion fold können wir eine Liste zu einem einzigen Wert "zusammenfalten".
fold bekommt einen Wert, eine Funktion und eine Liste übergeben.
Die übergebene Funktion wird nacheinander auf jedes Listenelement angewandt, beginnend mit dem letzten
Listenelement und dem übergebenen Wert.
Ein fold-Ausdrucks in Racket besteht aus:
-
Dem Operator
fold - Einen Wert als ersten Operanden
- Einer Funktion als zweiten Operanden
- Einer Liste als dritten Operanden.
(fold wert funktion liste)Die übergebene Funktion erhält nacheinander als ersten Parameter alle Elemente der übergebenen Liste und als zweiten Parameter entweder den übergebenen Wert oder die Rückgabe der vorangegangenen Funktionsausführung. Daher gelten die folgenden Einschränkungen:
Wenn die Liste Elemente vom Typ
%a beinhaltet und die Funktion ein Datum vom
Typ %b zurückgibt. So muss der Wert ebenfalls vom Typ %b sein
und die Funktion von der Signatur %a %b -> %b.
Für die Funktion
fold ergibt sich somit die Signatur:
(%b (%a %b -> %b) (list-of %a) -> %b).
Beispiele:
1. Der Ausdruck
(fold 0 + (list 4 7 5 6 9))entspricht:
(natural (number number -> number) (list-of natural) -> natural)
2. Der Ausdruck
(fold "Problem." string-append (list "Das " "ist " "kein "))entspricht:
(string (string string -> string) (list-of string) -> string )
3. Der Ausdruck
(fold 0 (lambda (w x) (+ (string-length w) x)) (list "Hallo" "Welt" "!"))entspricht:
(number (string number -> number) (list-of string) -> number )