Listenoperationen

Anleitung

Implementiere grundlegende Listenoperationen.

In funktionalen Sprachen sind Listenoperationen wie length, map und reduce sehr verbreitet. Implementiere eine Reihe grundlegender Listenoperationen, ohne vorhandene Funktionen zu verwenden.

Die genaue Anzahl und die Namen der Operationen, die du implementieren sollst, hängen vom jeweiligen Track ab, damit es keine Konflikte mit vorhandenen Namen gibt. Die allgemeinen Operationen, die du implementierst, sind:

• append (füge bei zwei gegebenen Listen alle Elemente der zweiten Liste ans Ende der ersten Liste an);
• concatenate (kombiniere bei einer Reihe von Listen alle Elemente aller Listen zu einer einzigen flachen Liste);
• filter (gib bei einem Prädikat und einer Liste die Liste aller Elemente zurück, für die predicate(item) True ist);
• length (gib bei einer Liste die Gesamtzahl der darin enthaltenen Elemente zurück);
• map (gib bei einer Funktion und einer Liste die Liste der Ergebnisse zurück, die du erhältst, wenn du function(item) auf alle Elemente anwendest);
• foldl (wenn du eine Funktion, eine Liste und einen Anfangswert für den Akkumulator hast, falte (reduziere) jedes Element von links in den Akkumulator);
• foldr (wenn du eine Funktion, eine Liste und einen Anfangswert für den Akkumulator hast, falte (reduziere) jedes Element von rechts in den Akkumulator);
• reverse (gib bei einer Liste eine Liste mit allen ursprünglichen Elementen zurück, aber in umgekehrter Reihenfolge).

Beachte, dass die Reihenfolge, in der die Argumente an die fold-Funktionen (foldl, foldr) übergeben werden, wichtig ist.

Moment, das ist unmöglich!

Diese Listenoperationen zu implementieren, ohne irgendeine eingebaute Funktion zu verwenden, ist in Roc praktisch unmöglich, denn du brauchst eine Möglichkeit, Elemente an eine Liste anzuhängen oder ihr welche voranzustellen. In anderen Sprachen könntest du Operatoren wie : in Haskell oder += in Python verwenden, aber in Roc musst du die List-Funktionen benutzen.

Für diese Übung darfst du also List.append verwenden (aber vermeide jede andere eingebaute Funktion).

Viele funktionale Programmiersprachen verwenden verkettete Listen als primären Sammlungstyp. Bei einer verketteten Liste ist es effizient, ein Element voranzustellen oder das erste Element zu entfernen, deshalb würdest du Listenoperationen in diesen Sprachen mit List.prepend implementieren. In Roc ist eine List jedoch ein Array (ein zusammenhängender Block von Bytes). Arrays haben andere Eigenschaften als verkettete Listen, zum Beispiel die Möglichkeit, effizient über einen Index auf Elemente zuzugreifen und neue Elemente anzuhängen. Deshalb verwenden wir in Roc häufig List.append und nur selten List.prepend.

Benennung

Roc verwendet etwas andere Namen als die in den allgemeinen Anweisungen aufgeführten:

• concat statt append
• join statt concatenate
• len statt length
• fold statt foldl
• fold_rev statt foldr

Die folgenden Funktionsnamen sind in Roc jedoch Standard:

• filter
• map
• reverse

Hinweis

Versuche Folgendes:

match list {
    [] => ...
    [first, .. as rest] => ...
}

oder

match list {
    [] => ...
    [.. as rest, last] => ...
}