Funkcja dodawania listy rekursji ogonowej

Question

Widzę kilka przykładów implementacji append elementu do listy, ale wszystkie nie używają rekurencji ogona. jak wdrożyć taką funkcję w stylu funkcjonalnym?

(define (append-list lst elem) expr) 

Answer 1

Dobrze jest można napisać procedurę ogon rekurencyjnej append-element ...

(define (append-element lst ele) 
    (let loop ((lst (reverse lst)) 
      (acc (list ele))) 
    (if (null? lst) 
     acc 
     (loop (cdr lst) (cons (car lst) acc))))) 

... ale to bardziej nieefektywne z tego reverse wrzucony (na wszelki wypadek). Nie mogę wymyślić innego funkcjonalnego (np. Bez modyfikowania listy wejściowej) sposobu napisania tej procedury jako rekursji ogonowej bez wcześniejszego odwrócenia listy.

Dla niefunkcjonującej odpowiedź na to pytanie, @WillNess dostarczyła przyjemne rozwiązanie Scheme mutujące listę wewnętrzną.

Answer 2

To Lisp, nie Scheme, ale jestem pewien, że można przetłumaczyć:

(defun append-tail-recursive (list tail) 
    (labels ((atr (rest ret last) 
      (if rest 
       (atr (cdr rest) ret 
         (setf (cdr last) (list (car rest)))) 
       (progn 
        (setf (cdr last) tail) 
        ret)))) 
    (if list 
     (let ((new (list (car list)))) 
      (atr (cdr list) new new)) 
     tail))) 

trzymam głowę i ogon listy powrotnej i modyfikować ogon jak przemierzać lista jej argumentów.

Answer 3

Poniżej przedstawiono implementację optymalizacji tail recursion modulo cons, w wyniku której uzyskano w pełni ogonowy kod rekurencyjny. Kopiuje strukturę wejściową, a następnie dołącza do niej nowy element, poprzez mutację, w sposób odgórny. Ponieważ mutacja ta jest wykonywana na jego wewnętrznych świeżo utworzonych danych, jest nadal funkcjonalny na zewnątrz (nie zmienia żadnych danych przekazywanych do niego i nie ma skutków obserwowalne wyjątkiem wytwarzania jej wynik):

(define (add-elt lst elt) 
    (let ((result (list 1))) 
    (let loop ((p result) (lst lst)) 
     (cond 
     ((null? lst) 
      (set-cdr! p (list elt)) 
      (cdr result)) 
     (else 
      (set-cdr! p (list (car lst))) 
      (loop (cdr p) (cdr lst))))))) 

lubię używając sztuczki "head-sentinel", znacznie upraszcza kod kosztem alokacji tylko jednej dodatkowej komórki.

Ten kod używa prymitywów mutacji niskiego poziomu, aby osiągnąć to, co w niektórych językach (np. Prolog) jest wykonywane automatycznie przez kompilator. W TRMC optymalizacja hipotetycznego projektu, będziemy mogli napisać następujące ogon rekurencyjnej modulo minusy kod i mieć kompilator automatycznie przetłumaczyć je na jakiś odpowiednik powyższego kodu:

(define (append-elt lst elt)    ;; %% in Prolog: 
    (if (null lst)       ;; app([], X, Z) :- Z=[X]. 
    (list elt)       ;; app([A|B], X, Z) :- 
    (cons (car lst)      ;; Z=[A|Y],   % cons _before_ 
      (append-elt (cdr lst) elt)))) ;; app(B, X, Y). % tail call 

Jeśli nie dla cons operacja, append-eltbędzie być rekurencyjne. Tutaj zaczyna działać optymalizacja TRMC.

Answer 4

Nie można naiwnie, ale zobacz także implementacje zapewniające TCMC - Tail Call Modulo Cons. To pozwala

(cons head TAIL-EXPR) 

do ogona połączenia TAIL-EXPR Jeżeli sam wad jest ogon połączenia.

Answer 5

Jest to funkcjonalny, ogon rekurencyjnej append-ELT użyciu kontynuacje:

(define (cont-append-elt lst elt) 
    (let cont-loop ((lst lst) 
        (cont values)) 
    (if (null? lst) 
     (cont (cons elt '())) 
     (cont-loop (cdr lst) 
        (lambda (x) (cont (cons (car lst) x))))))) 

Performance-mądry to blisko Will mutacji jeden w Racket i Gambit ale w Ikarus i reverse Chicken Oscar jest nie lepiej. Mutacja zawsze była jednak najlepsza. Nie skorzystałbym jednak z tego, ale niewielka wersja zapisu Óscar, ponieważ jest łatwiejsza do odczytania.

(define (reverse-append-elt lst elt) 
    (reverse (cons elt (reverse lst)))) 

A jeśli chcesz mutacji wydajność bym zrobiła!!!

(define (reverse!-append-elt lst elt) 
    (let ((lst (cons elt (reverse lst)))) 
    (reverse! lst) 
    lst))