Strukturierung: Funktionen höherer Ordnung
Funktionen die Funktionen verarbeiten
Um einige Probleme elegant zu lösen, kann es hilfreich sein, Funktionen zu entwerfen, die selbst Funktionen als Übergabedaten erhalten oder Funktionen als Rückgabe liefern. In der funktionalen Programmierung ist das ganz natürlich möglich, wir können Funktionen hier wie jeden anderen Datentyp behandeln.
Aufgabe 1: Bekannte Funktionen höherer Ordnung
(a) Betrachte die in dieser Datei verwendeten bzw. definierten Funktionen. Sammle sämtliche Funktionen höherer Ordnung, die du findest.
(b) Begründe, warum Funktionen höherer Ordnung bei der Anwendung auf Listen besonders nützlich sind.
Aufgabe 2: Signaturen von Funktionen höherer Ordnung
Ob es sich bei einer Funktion um eine Funktion höherer Ordnung handelt, wird anhand
der Funktionssignatur direkt ersichtlich.
Betrachten wir unsere Funktion infix mit einer zulässigen Signatur:
(: infix (real (real real -> real) real -> real))
(define infix
(lambda (x f y)
(f x y)))
(a) Woran erkennst du in der Signatur, dass es sich um eine Funktion höherer Ordnung handelt?
(b) Ergänze die obige Signatur für deine Funktion infix.
Teste und begründe anschließend, welche der folgenden drei Aufrufe anhand der Signatur zulässig sind.
> (infix -18.2 max -20)
> (infix "Hallo " string-append "Welt!")
> (infix 14 < 13)
(c) Passe die Signatur so an, dass diese für sämtliche der drei Ausdrücke zulässig ist.
Tipp: Wenn du dir unsicher bist, schau dir die Signaturen von Listenfunktionen
nochmals an.
(d) Ergänze die Signaturen für deine in diesem Kapitel erstellten Funktionen höherer Ordnung:
prefixpostfixgetFunc
Aufgabe 3: Die Alleskönner-Funktion fold
Mit map, filter und fold haben
wir bereits drei häufig genutzte Funktionen höherer Ordnung kennengelernt.
Genau genommen reicht jedoch eine dieser drei Funktionen aus, und zwar fold.
Denn mit Hilfe von fold lassen sich sowohl map
als auch filter nachbauen.
Hinweis: Sowohl für Aufgabenteil (a) als auch (b) finden sich am Ende dieser Aufgabe Hilfestellungen.
(a) Schreibe die Funktion mein-map, die dieselbe Funktionalität
wie die Funktion map liefern soll. Zur Implementierung darfst du weder
map noch filter nutzen.
(b) Schreibe die Funktion mein-filter, die dieselbe Funktionalität
wie die Funktion filter liefern soll. Zur Implementierung darfst du weder
map noch filter nutzen.
Hilfestellung 1:
Die an fold übergebene Funktion wird nacheinander auf jedes Element
der übergebenen Liste angewandt. Beginnend mit dem letzten Listenelement und dem übergebenen Wert.
(fold 0 + (list 1 2 3))
;entspricht also:
(+ 1 (+ 2 (+ 3 0)))
fold übergeben kannst,
um als Endresultat wieder eine Liste zu erhalten.
Hilfestellung 2:
Der folgende fold-Ausdruck, gibt
eine Liste zurück, die identisch zur übergebenen Liste ist.
(fold empty cons (list 1 2 3 4))
cons als übergebene Funktion im fold-Ausdruck nicht ausreichend.
Ersetzte cons durch eine von dir geschriebene Funktion,
die neben cons auch die an mein-map bzw.
mein-filter übergebene Funktion auf die Elemente anwendet. Hilfestellung 3 - map:
Der folgende fold-Ausdruck, gibt
eine Liste zurück, die dem Ergebnis von
(map natural? (list -2 -1 0 1 2)) entspricht.
(fold
empty
(lambda (x li) (cons (natural? x) li))
(list -2 -1 0 1 2)
)
Hilfestellung 3 - filter:
Mit der Funktion cons sorgen wir dafür, dass Elemente an eine Liste
angehängt werden. Um filter erfolgreich zu implementieren, müssen wir
sicherstellen, dass cons nur auf die Elemente angewandt wird, die
die geforderte Bedingung erfüllen.
Hilfestellung 4 - filter:
Der folgende fold-Ausdruck, gibt
eine Liste zurück, die dem Ergebnis von
(filter natural? (list -2 -1 0 1 2)) entspricht.
(fold
empty
(lambda (x li) (if [natural? x] (cons x li) li))
(list -2 -1 0 1 2)
)
