Ansatz:
Ermitteln und Programmieren der Basis- Abbruch- Fälle
unmittelbare Bestimmung des Ergebnis für Eingabeparameter möglich
Programmieren der rekursiven Fälle
Grundschema
Grundrezept rekursiver Listenbearbeitung
Nimm Anfang Liste mache etwas
rufe Funktion rekursiv auf Rest der Liste auf
für übersichtlicheren und kürzeren Code
Rekursions Code für typische Listen Funktionen
in allen Programmiersprachen mit funktionalen Konzepten enthalten
Python, Java, Lisp, C#…
wende Funktion auf alle Listenelemente an
Runde alle Zahlen
Liste entsprechend bestimmter bool’schen Funktion filtern
alle Zahlen kleiner Pivot
Alle Elemente einer Liste mit bestimmter Funktion kombinieren
addieren alle Zahlen einer Liste
(map f list1 list2 …)
Parameter
Funktion f
beliebige Anzahl an Listen als Parameter, müssen gleich lang sein
Anzahl Argumente der Funktion muss gleich der Anzahl der übergebenen Listen sein
Wendet Funktion auf alle ersten, zweiten.. Listenelemente an, gibt Ergebnisliste zurück
(filter pred list)
einstelliges Prädikat als ersten Parameter
einstellige Funktion, die true oder false zurückgibt
Liste als zweiter parameter
(foldl f init l1 …) und (foldr f init l1 …)
fild heißt in Java/ Python.. reduce
Initialwert init
beliebig viele Listen gleicher Länge
Anzahl Argumente f muss um 1 größer sein als Anzahl der Listen
Anwendung f zunächst auf alle ersten Listenelemente und den Initialwert an, dann auf alle zweiten Listenelemente und auf das Ergebnis des ersten Aufrufs
kombinieren in jedem Schritt das aktuelle Listenelement mit einem aktuellen Zwischenergebnis zu einem neuen Zwischenergebnis
foldl und foldr iterieren eine Liste von links nach rechts bzw. umgekehrt
fold-Funktionen sind die mächtigsten der üblichen Built-In-HOFs auf Listen
map und filter bloß Spezialfälle von fold
ähnlich for-, foreach- und do-while-Schleifen Spezialfälle von while
map und foldl/foldr können mehrere Listen als Parameter nehmen, solange die Stelligkeit der Funktion f dazu passt
auch die Datentypen der verschiedenen Listen können voneindander abweichen, solange die Datentypen der Parameter der Funktion f dazu passen!
bei foldl und foldr darf auch der Datentyp des Initalwerts (und damit der Zwischenergebnisse und des Endergebnisses) nochmal ein anderer sein, ebenfalls, solange die Funktion f dazu passt
apply ist eine HOF, die eine beliebige n-stellige Funktion und eine Liste der L ̈ange n als Parameter nimmt und die Funktion f auf die Werte in der Liste anwendet
hin und wieder hat man die Situation, dass man eine Funktion auf Parameter anwenden möchte, die als Liste vorliegen
Ein Baum ist entweder ein Atom (ein Blatt!) oder eine Liste bestehend aus dem Wurzelknoten als erstem Element und beliebig vielen Unterbäumen (Elemente der Restliste).
Wir repräsentieren Bäume mittels vernesteter Listen
Welche vier wichtigen Built-In-HOFs gibt es in Racket (und in anderen Sprachen mit funktionalen Programmierkonzepten)?
Welche Parameter mit welchen Bedeutungen haben diese Funktionen?
Was macht die Built-In-Funktion apply?
Auf welche Art und Weise kann man Bäume mittels vernesteter Listen repräsentieren? Zeichnen Sie folgenden Baum: ’(a (b d (e f g) h) (c i j))
Last changed7 months ago