Blatt 5

Bei den folgenden Aufgaben sollen Sie Gebrauch machen von Standardfunktionen zur Listenverarbeitung wie take, map, fold, filter, ...

1.

Geben Sie so eine neue Definition der ``how_many'' Funktion des Beispiels aus 3.3.

2.

Eine Liste wird sortiert, indem man sie in zwei (im Idealfall gleich große) Teillisten zerlegt, diese (nach demselben Verfahren) sortiert und dann wieder in geeigneter Weise vereinigt, z.B.:

(a)

merge sort:

Teilung = Halbierung der Liste,
Vereinigung = ordnungstreue Verzahnung (``merge'') der beiden sortierten Listen.

(b)

quick sort:

Teilung durch Vergleich mit Trennelement (z.B. erstes Element der Liste),
Vereinigung durch Konkatenation der sortierten Listen.

(Hinweis: man kann die Aufspaltung mit zwei ``filter'' Anwendungen, aber vielleicht auch in einem Durchlauf machen).

3.

Um die Liste aller Permutationen einer Liste x:xs zu berechnen (das ist dann eine Liste von Listen), kann man wie folgt vorgehen:

erstens, finde alle Permutationen von xs,
zweitens, setze x auf alle denkbaren Weisen in jede der Permutationen ein.