4. Listen

4.5 Listen verarbeiten mit `map, filter, fold`

Falls das letzte Kapitel Sie verunsichert hat und das Umformen in endrekursive Versionen Ihr Gehirn verknotet hat, so kommt nun Hilfe. Der der Realität lässt sich Rekursion tatsächlich in den meisten Fällen vermeiden, bzw. an eine Handvoll rekursiver Basisfunktionen "auslagern". Wir beginnen mit einer Übung, die Ihnen jetzt eigentlich leicht fallen sollte:

Übungsaufgabe Schreiben Sie folgende drei Funktionen (wenn Sie das nicht bereits getan haben):

incrementAll : List Int -> List Int, die jedes Element um 1 erhöhen soll;
doubleAll, die jedes Element verdoppeln soll;
labelAsPrime : List Int -> List (Int, Bool), die jede Zahl in der Eingabeliste mit True/False als Primzahl oder Nichtprimzahl labeln soll:
```
labelAsPrime [3,4,5,6,7,8,9]        
[(3,True),(4,False),(5,True),(6,False),(7,True),(8,False),(9,False)]
    : List ( Int, Bool )
```

Achten Sie nicht auf Endrekursion, denn darum geht es hier nicht.

Ist Ihnen etwas aufgefallen? Sie haben im Prinzip dreimal fast den gleichen Code geschrieben. Denn alle drei Funktionen machen fast das gleiche: sie wenden eine Funktion auf jedes Element in einer Liste an. Kann man das auslagern? Ja, wenn man Funktionen als Eingabewerte zulässt:

applyToEach : (a -> b) -> List a -> List b
applyToEach f list =
    case list of
        [] ->
            []

        x :: rest ->
            f x :: applyToEach f rest

Jetzt brauchen Sie sich für incrementAll, doubleAll, labelAsPrime keinen rekursiven Code mehr schreiben. Sie müssen einach applyToEach richtig aufrufen:

labelAsPrime : List Int -> List ( Int, Bool )
labelAsPrime list =
    let
        labelOneNumber : Int -> ( Int, Bool )
        labelOneNumber n =
            ( n, isPrime n )
    in
    applyToEach labelOneNumber list

Übungsaufgabe Schreiben Sie eine endrekursive Version von applyToEach. Sie sollten locker Listen der Länge 20000 damit verarbeiten können.

Ab jetzt müssen Sie nicht mehr Ihre selbst geschrieben Funktion applyToEach verwenden, sondern dürfen die vorgefertige Funktion List.map verwenden:

List.map                        
<function> : (a -> b) -> List a -> List b

Ähnlich zur Funktion applyToEach bzw. List.map ist die Funktion keepOnlyThoseWith, die aus einer Liste nur diejenigen Elemente übernimmt, die eine bestimmte Bedingung erfüllen, beispielsweise

keepOnlyThoseWith isPrime [1,2,3,4,5,6,7,8,9]                        
[2,3,5,7] : List Int

Übungsaufgabe Implementieren Sie keepOnlyThoseWith.

Auch hier gibt es die bereits vorgefertigte Funktion List.filter:

List.filter                        
<function> : (a -> Bool) -> List a -> List a
List.filter Char.isLower (String.toList "Guten Morgen")
['u','t','e','n','o','r','g','e','n'] : List Char

Die Funktionen `List.foldl` und `List.foldr`

Wir kommen nun zur konzeptuell schwierigsten Listenfunktion. Als motivierendes Beispiel wollen wir alle Zahlen einer Liste aufaddieren:

addAll [1,3,4,5]
13

Hier ist der dazugehörige Code:

addAll : List Int -> Int
addAll list =
    case list of
        [] ->
            0

        x :: rest ->
            x + addAll rest

und zwei Testaufrufe:

addAll (List.range 1 1000)                        
500500
addAll (List.range 1 10000)
RangeError: Maximum call stack size exceeded

Tja, der Code von addAll ist natürlich nicht endrekursiv, daher scheitert er bereits an moderat langen Listen.

Übungsaufgabe Schreiben Sie eine endrekursive Funktion addAll2.

Meine Lösung

Das geht natürlich wieder mit der berühmten Zwischenergebnisvariable:

addAll2 : Int -> List Int -> Int
addAll2 start list =
    case list of
        [] ->
            start

        x :: rest ->
            addAll2 (start + x) rest

Und jetzt gehen große Listen:

addAll2 0 (List.range 1 10000)                                
50005000 : Int

Ganz allgemein wollen wir die Möglichkeit haben

mit einem Startwert start vom Typ b zu beginnen (hier: 0);
die Listenelemente, die vom Typ a sind, eins nach dem anderen mit einer Kombinatorfuktion combine (hier: +) auf das Zwischenergebnis "draufaddieren" und einen neuen b-Wert zu erhalten;
das Endergebnis zurückzugeben.

Hier ist mein Code:

combineAll : (a -> b -> b) -> b -> List a -> b
combineAll f start list =
    case list of
        [] ->
            start

        x :: rest ->
            f x (combineAll f start rest)

Und hier wieder die endrekursive Version:

combineAll2 : (a -> b -> b) -> b -> List a -> b
combineAll2 f start list =
    case list of
        [] ->
            start

        x :: rest ->
            combineAll2 f (f x start) rest

Ein kleines Detail: die Funktionen combineAll und combineAll2 wollen als erstes Argument die Kombinatorfunktion f. Wenn wir also beispielsweise alle Zahlen aufaddieren wollen, brauchen wir eine Funktion, die zwei Zahlen addiert. Die gibt es schon: +. Allerdings geht + mit Infixschreibweise, also 2 + 3 statt + 2 3, die Funktion f steht in Zeilen 272 bzw. 282 allerdings in Präfixnotation. In Elm gibt es die Funktion (+), die nichts anderes ist als + als normale Präfix-Funktion. Daher also:

(+)                        
<function> : number -> number -> number
(+) 3 5
8 : number
combineAll (+) 0 [1,2,3,4]
10
combineAll2 (+) 0 [1,2,3,4]
10
combineAll (+) 0 (List.range 1 10000)
RangeError: Maximum call stack size exceeded
combineAll2 (+) 0 (List.range 1 10000)
50005000 : Int

Die Version combineAll2 ist also besser, weil sie endrekursiv ist. Schauen wir uns ein zweites Beispiel an. Wir wollen eine List Int als Dezimalzahl interpretieren und in ein Int umwandeln, also

listToDecimal [1,5,3,7]
1537 : Int

Wir kombinieren ein "Zwischenergebnis" s, beispielsweise 153, mit einem neuen Listenelement x (beispielsweise 7), indem wir 10* + x berechnen. Wir müssen uns nur daran erinnern, dass die Kombinatorfunktion f zuerst das Listenelement will (vom Typ a), dann das Zwischenergebnis (vom Typ b):

comb: Int -> Int -> Int                    
comb x s = x + 10*s                        
combineAll2 comb 0 [1,5,3,7]
1537 : Int

Schematisch passiert das folgende:

Das Problem ist nun, dass combineAll2 und combineAll nicht mehr das gleiche tun:

combineAll2 comb 0 [1,5,3,7]
7351 : Int

In diesem Fall scheint das Ergebnis von combineAll2 zu stimmen, allerdings gibt es gute Gründe, große Zahlen so darzustellen, dass die "kleinen" Stellen am Anfang der Liste kommen. Schematisch gesehen tun combineAll das hier:

Beide Funktionen sind nützlich, je nach Kontext. Es gibt sie bereits unten den Namen List.foldl und List.foldr. Nochmal zur Übersicht:

Die Funktion `List.foldl`

Die Funktion `List.foldr`

Übungsaufgabe Schreiben Sie eine endrekursive Version von combineAll. Achtung: die Funktion combineAll2 ist zwar endrekursiv, tut aber Anderes! Die Lösung ist etwas trickreicher (oder dümmer, je nach Sichtweise).

Übungsaufgabe Schreiben Sie eine Funktion leftToRightMaxima, die für eine Liste die "bisher größten" Elemente rausfiltern. Beispiel:

leftToRightMaxima [1,3,6,2,3,8]                            
[1,3,6,8]

Die Elemente 1, 3, 6 werden übernommen, weil jedes von ihnen das bisher größte war. Das vierte Element, also 2, wird nicht übernommen, weil wir bereits etwas größeres gesehen haben (zum Beispiel 3 oder 6). Verwenden Sie keine Rekursion, sondern nur vorgefertige Funktionen wie List.map, List.filter, List.foldl, List.foldr, List.reverse.

Tip: kriegen Sie Ihre Datentypen auf die Reihe. Was ist a, der Typ Ihrer Eingabelistenelemente? Das ist Int. Was ist b, der Rückgabewert von List.foldl und List.fodlr und somit wohl Ihr Rückgabewert? Wir wollen als Ergebnis eine Liste, also ist b der Type List Int. Somit ist klar, wie die Kombinatorfunktion auszusehen hat:

f : Int -> List Int -> List Int

Ein Aufruf von f hat also das Schema f neuesElement jetzigeErgebnisListe. Jetzt müssen Sie sich überlegen, was f sein soll.

Übungsaufgabe Schreiben Sie eine Funktion, die die Elemente einer Liste durchnumeriert:

numberItems 1 ["monday", "tuesday", "wednesday"]                            
[(1, "monday"), (2, "tuesday"), (3, "wednesday")]

Gehen Sie systematisch vor. In der Signatur von List.foldl : <function> : (a -> b -> b) -> b -> List a -> b, was ist in Ihrem Fall a und was ist b?

Übungsaufgabe Re-implementieren Sie die Funktionen List.map und List.filter ohne Rekursion, nur mithilfe der Funktionen List.foldl und List.foldr.

Übungsaufgabe Implementieren Sie eine endrekursive Funktion loop n f x, die die Funktion \(f\) \(n\)-mal auf einen Startwert anwendet.

add_x : String -> String
add_x s = s ++ "x"
loop 10 add_x "hello"
"helloxxxxxxxxx" : String

4. Listen

4.5 Listen verarbeiten mit map, filter, fold

Die Funktionen List.foldl und List.foldr

Die Funktion List.foldl

Die Funktion List.foldr

4.5 Listen verarbeiten mit `map, filter, fold`

Die Funktionen `List.foldl` und `List.foldr`

Die Funktion `List.foldl`

Die Funktion `List.foldr`