Das Folgende ist eine Implementierung der Optimierung von Tail-Recursion-Modulo-Contras , die zu einem vollständig rekursiven Tail-Code führt. Es kopiert die Eingabestruktur und fügt dann das neue Element durch Mutation top-down hinzu. Da diese Mutation mit ihren internen frisch erzeugten Daten gemacht wird, ist sie immer noch funktional (ändert nichts an Daten, die in sie hineingelangt sind und hat keine beobachtbaren Auswirkungen, außer dass sie ihr Ergebnis erzeugt):
%Vor%Ich mag es, einen "Head-Sentinel" -Trick zu verwenden, der den Code erheblich vereinfacht, und zwar auf Kosten der Zuweisung von nur einer zusätzlichen Zelle.
Dieser Code verwendet Low-Level-Mutationsprimitive, um zu erreichen, was in einigen Sprachen (z. B. Prolog) automatisch von einem Compiler erledigt wird. In einem TRMC-optimierenden hypothetischen Schema könnten wir den folgenden tail-rekursiven Modulo-Cons -Code schreiben und einen Compiler automatisch in eine Entsprechung des obigen Codes übersetzen lassen:
%Vor% Wenn nicht für die Operation cons , wäre append-elt
Nun ist möglich, eine tail-rekursive append-element Prozedur zu schreiben ...
... aber es ist ineffizienter mit dem reverse (in gutem Maße). Ich kann nicht an ein anderes funktionelles denken (z. B. ohne die Eingabeliste zu ändern), um diese Prozedur als Tail-Recursion zu schreiben, ohne die Liste zuerst umzukehren.
Für eine nicht funktionale Antwort auf die Frage lieferte @WillNess eine nette Schema-Lösung, die eine interne Liste mutierte.
Dies ist eine funktionale, tail rekursive append-elt mit Fortsetzungen:
%Vor%In Sachen Leistung ist es Wills Mutation in Racket und Gambit sehr ähnlich, aber in Ikarus und Chicken Óscar lief es besser. Mutation war jedoch immer der beste Darsteller. Ich hätte das aber nicht benutzt, sondern eine leichte Version von Oscar's Eintrag, nur weil es einfacher zu lesen ist.
%Vor%Und wenn Sie die Performance verändern möchten, hätte ich Folgendes getan:
%Vor%Tags und Links scheme lisp racket tail-call-optimization tailrecursion-modulo-cons