umkehren der Liste in Lisp

Ihren code so geschrieben ist, ist logisch richtig und erzeugt das Ergebnis, das Sie wollen, es zu:

CL-USER> (defun rev (l)
           (cond
             ((null l) '())
             (T (append (rev (cdr l)) (list (car l)))))) 
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)

Sagte, es gibt einige Probleme mit ihm in Bezug auf Leistung. Die Anhängen - Funktion erzeugt eine Kopie von allen, aber seine endgültige argument. E. g., wenn Sie das tun (append '(1 2) '(a b) '(3 4)), erstellen Sie vier neue cons-Zellen, deren Wagen 1, 2, a, und b. Die cdr der Letzte der vorhandenen Liste (3 4). Das ist, weil die Umsetzung der Anhängen ist so etwas wie dieses:

(defun append (l1 l2)
  (if (null l1)
      l2
      (cons (first l1)
            (append (rest l1)
                    l2))))

Das ist nicht gerade Common Lisp ist Anhängen, da Common Lisp ist Anhängen können mehr als zwei Argumente. Es ist nahe genug, um zu demonstrieren, warum alle, aber die Letzte Liste kopiert, obwohl. Schauen Sie sich jetzt was das bedeutet in Bezug auf Ihre Umsetzung rev, aber:

(defun rev (l)
  (cond
    ((null l) '())
    (T (append (rev (cdr l)) (list (car l)))))) 

Dies bedeutet, dass, wenn man die Umkehrung einer Liste wie (1 2 3 4), es ist wie du bist:

(append '(4 3 2) '(1))              ; as a result of    (1)
(append (append '(4 3) '(2)) '(1))  ; and so on...      (2)

Nun, in Zeile (2), Sie kopieren die Liste (4 3). In Zeile eins, Sie sind das kopieren der Liste (4 3 2), die eine Kopie von (4 3). Das ist, Sie sind kopieren eine Kopie. Das ist eine ziemlich verschwenderisch mit Speicher.

Eine weitere gemeinsame Ansatz verwendet eine Akkumulator-variable und eine Hilfsfunktion. (Beachten Sie, dass ich endp, rest, ersten, und Liste* statt null, cdr, Auto, und Nachteile, denn es macht es deutlicher, dass wir die Arbeit mit Listen, nicht willkürlich Nachteile-Bäume. Sie sind so ziemlich das gleiche (aber es gibt ein paar Unterschiede).)

(defun rev-helper (list reversed)
  "A helper function for reversing a list.  Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED.  (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
  (if (endp list)
      reversed
      (rev-helper (rest list)
                  (list* (first list)
                         reversed))))

CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)

Mit dieser Hilfsfunktion ist es einfach zu definieren, rev:

(defun rev (list)
  "Returns a new list containing the elements of LIST in reverse
order."
  (rev-helper list '()))

CL-USER> (rev '(1 2 3))
(3 2 1)

Sagte, dass, anstatt eine externe helper-Funktion, wäre es wahrscheinlich häufiger zu verwenden Etiketten so definieren Sie eine lokale Hilfsfunktion:

(defun rev (list)
  (labels ((rev-helper (list reversed)
             #| ... |#))
    (rev-helper list '())))

Oder, da Common Lisp ist nicht garantiert Optimierung Schwanz Anrufe, eine tun loop ist schön und sauber, auch hier:

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))

InformationsquelleAutor Joshua Taylor

Wenn Sie können, verwenden Sie die standard-CL-Bibliothek Funktionen wie append, sollten Sie reverse (wie Kaz vorgeschlagen).

Sonst, wenn dies ist eine übung (h/w oder nicht), können Sie versuchen, diese:

(defun rev (l)
  (labels ((r (todo)
             (if todo
                 (multiple-value-bind (res-head res-tail) (r (cdr todo))
                   (if res-head
                       (setf (cdr res-tail) (list (car todo))
                             res-tail (cdr res-tail))
                       (setq res-head (list (car todo))
                             res-tail res-head))
                   (values res-head res-tail))
                 (values nil nil))))
    (values (r l))))

PS. Ihre spezifischen Fehler nicht nachvollziehbar ist, Kontaktieren Sie bitte Ihren Händler.

InformationsquelleAutor sds