4. Listen

4.3 Listen umdrehen, sortieren etc.

In der letzten Übungsaufgabe haben Sie eine Funktion geschrieben, die eine Liste umdreht. Hier sehen Sie meine Lösung. Als erstes brauche ich eine Funktion append, die zwei Listen miteinander verknüpft:

append : List a -> List a -> List a
append list1 list2 =
    case list1 of
        [] ->
            list2

        x :: rest ->
            x :: append rest list2

In Worten: wenn list1 leer ist, dann ist das Ergebnis einfach list2, wie in Zeilen 4-5 beschrieben. Wenn list1 nichtleer ist und mit x beginnt und dann eine Restliste rest hat, dann verknüpfe ich erstmal rest mit list2 (rekursiver Aufruf) und klebe dann schlussendlich x vorne dran. Das geschieht in Zeilen 7-8.

Wie schreibe ich nun meine Funktion reverse, die eine Liste umdreht? Einfach: wenn die Eingabelist list die Struktur x :: rest hat, dann muss ich erst mal rest umdrehen und dann x hinten anhängen:

reverse : List a -> List a
reverse list =
    case list of
        [] ->
            []

        x :: rest ->
            let
                restReversed : List a
                restReversed =
                    reverse rest
            in
            append restReversed [ x ]

Übungsaufgabe Zeichnen Sie den Rekursionsbaum von reverse [1,2,3,4]. Zeichnen Sie also für jeden Aufruf von reverse und append einen Knoten. Ich mach hier mal den Anfang:

Übungsaufgabe Schreiben Sie eine Funktion insertIntoSorted : Int -> List Int -> List Int, die in eine aufsteigend sortierte Liste von Zahlen eine neue Zahl an die richtige Stelle einfügt:

insertIntoSorted 3 [1,4,9,16]                            
[1, 3, 4, 9, 16] : List Int

Übungsaufgabe Schreiben Sie mit Hilfe von insertIntoSorted eine Funktion insertionSort : List Int -> List Int, die eine Liste sortiert.