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#…

MAP

• wende Funktion auf alle Listenelemente an

  • Runde alle Zahlen

FILTER

• Liste entsprechend bestimmter bool’schen Funktion filtern

  • alle Zahlen kleiner Pivot

REDUCE

• 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)

Parameter

• 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

Parameter

1. Funktion f

2. Initialwert init

3. 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