Ich bin ein Anfänger, der Erlang lernt. Nachdem ich in Erlang über List Comprehensions und Rekursion gelesen hatte, wollte ich versuchen, meine eigene map -Funktion zu implementieren, die so aussah:
Meine Frage ist: Es fühlt sich falsch an, eine Liste durch die rekursive Funktion aufzubauen und sie dann am Ende umzukehren. Gibt es eine Möglichkeit, die Liste in der richtigen Reihenfolge aufzubauen, also brauchen wir nicht das Gegenteil?
Um zu verstehen, warum das Ansammeln und Rückwärtsfahren ziemlich schnell ist, müssen Sie verstehen, wie Listen in Erlang erstellt werden. Erlangs Listen wie die in Lisp sind aus Cons-Zellen aufgebaut (siehe das Bild im Link).
In einer einfach verknüpften Liste wie den Erlang-Listen ist es sehr billig, ein Element (oder eine kurze Liste) voranzustellen. Dies ist das List = [H|T] -Konstrukt.
Das Umkehren einer einfach verknüpften Liste von Cons-Zellen ist ziemlich schnell, da Sie nur einen Durchlauf entlang der Liste benötigen, indem Sie das nächste Element an Ihr bereits umgekehrtes Teilergebnis anhängen. Und wie bereits erwähnt, wird es auch in C in Erlang implementiert.
Auch das Erstellen eines Ergebnisses in umgekehrter Reihenfolge kann oft durch eine tail rekursive Funktion erreicht werden, was bedeutet, dass kein Stack aufgebaut ist und ( nur in alten Versionen von Erlang! ) daher Speicher gespart werden kann .
Nachdem all dies gesagt wurde: Es ist einer der acht Mythen von Erlang Performance , dass es Es ist immer besser, umgekehrt in einer Tail Recursive-Funktion aufzubauen und lists:reverse/1 am Ende aufzurufen.
Hier ist eine rekursive Body-Version ohne lists:reverse/1 , dies würde mehr Speicher für Erlang-Versionen vor 12 benötigen, aber nicht für aktuelle Versionen:
Und hier ist eine Version der Karte mit List Comprehensions:
%Vor% Wie Sie sehen, ist dies so einfach, weil map nur ein Teil des Listenverständnisses ist, also würden Sie das Listenverständnis direkt verwenden und nicht mehr map benötigen.
Als Extra eine reine Erlang-Implementierung, die zeigt, wie man eine Liste von Cons-Zellen effizient bearbeiten kann (in Erlang ist es immer schneller, lists:reverse/1 aufzurufen, weil es in C ist, aber dasselbe tut).
Wie Sie sehen können, gibt es nur [A|B] -Operationen in der Liste, wobei Cons-Zellen voneinander getrennt sind (wenn Mustervergleiche) und Neu erstellen, wenn [H|Acc] ausgeführt wird.
Tags und Links erlang tail-recursion