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.

Implementierung

Für diese Übung musst du parametrischen Polymorphismus in Odin verwenden (gebräuchlicher ist der Begriff Generics). Wenn du dieses Feature noch nicht kennst, findest du hier einen kurzen Überblick, um loszulegen.

Parametrischer Polymorphismus ist eine Funktion von Programmiersprachen, die es Programmierenden ermöglicht, weniger spezifisch (also generischer, daher der Name) bei den Typen zu sein, die sie in ihrem Code verwenden, und trotzdem die Typsicherheit zu wahren. Das ergibt natürlich nur bei stark typisierten Sprachen wie Odin Sinn.

Fangen wir mit einem Beispiel an. Angenommen, du möchtest alle Elemente eines Arrays um einen festen Wert erhöhen, ein einfaches Problem.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Was aber, wenn du dieselbe Funktionalität nun auch für Gleitkommazahlen brauchst?

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Und dann für vorzeichenlose Ganzzahlen, 32-Bit-Gleitkommazahlen und so weiter?

Bald hast du eine ganze Reihe von Prozeduren, die genau dasselbe tun, aber mit unterschiedlichen Typen. Wenn du die Logik irgendwann ändern musst, musst du darauf achten, dass du es für alle Varianten tust, was zu viel Wartungsarbeit werden kann. Der andere Ärger ist, dass du jeder Prozedur einen anderen Namen geben musst, weil Odin kein implizites Überladen von Prozeduren unterstützt (du könntest immer noch explizites Überladen verwenden, aber das ist eine Geschichte für eine andere Übung).

Odin ist eine praktische Sprache und bietet mit parametrischem Polymorphismus eine Lösung. Solange der Compiler den Typ eines Parameters zur Kompilierzeit herausfinden kann, kannst du ihm einen generischen Namen geben, zum Beispiel T. Schreiben wir unsere obige Prozedur um:

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Beachte, dass wir alle Typannotationen (int oder f64) durch T ersetzt haben und dass vor dem ersten Vorkommen von T ein Dollarzeichen steht ($T). Der Typ $T sagt dem Odin-Compiler, dass der Name T ein generischer Name für den Typ ist, der während der Kompilierung durch den tatsächlichen Namen ersetzt wird. Und da der Compiler den generischen Typ T jetzt kennt, müssen die folgenden Vorkommen desselben Typs nur noch mit dem gewählten Typnamen (T) gekennzeichnet werden.

Du kannst jetzt Code wie diesen schreiben:

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

In der ersten Anweisung erkennt der Odin-Compiler den Typ des ersten Parameters ([]int) als den Typ des generischen Parameters ([]$T), folgert, dass T = int gilt, und kompiliert dann eine Version, in der alle folgenden Vorkommen von T durch int ersetzt sind (äquivalent zur spezialisierten Version incr_array_int() oben). Würdest du das Dollarzeichen in der Definition des ersten Parameters weglassen, hätte der Compiler im aktuellen Paket und in der Liste der Importe nach einem Typ namens T gesucht und höchstwahrscheinlich einen Kompilierfehler Error: Undeclared name: T zurückgegeben.

Die zweite Anweisung funktioniert genauso wie die erste, nur dass der Compiler T hier als f64 identifiziert.

Es ist üblich, generischen Typen einbuchstabige Namen zu geben (T und E werden oft verwendet).

Du solltest jetzt genug über parametrischen Polymorphismus, auch bekannt als generische Typen, wissen, um die Übung List Operations anzugehen.