反向LISP列表

Question

我想編寫一個反轉列表元素的函數，但它應該發生（即不要創建新的反轉列表）。

喜歡的東西：

>> (setq l ' (a b c d)) 
((a b c d) 
>> (rev l) 
(d c b a) 
>> l 
(d c b a) 

我應該遵循什麼標誌來實現這一目標？

Answer 1

實現這一點並不難（忽略故障情況）。關鍵是使用(setf cdr)來重新使用給定的缺陷單元，而不是丟失對先前的cdr的引用。

(defun nreverse2 (list) 
    (recurse reving ((list list) (rslt '())) 
    (if (not (consp list)) 
     rslt 
     (let ((rest (cdr list))) 
      (setf (cdr list) rslt) 
      (reving rest list))))) 

(defmacro recurse (name args &rest body) 
    `(labels ((,name ,(mapcar #'car args) ,@body)) 
    (,name ,@(mapcar #'cadr args)))) 

[編輯]作爲在留言中提到，要做到這一點真正就地（和W/O方面consing）：

(defun reverse-in-place (l) 
    (let ((result l)) 
    (recurse reving ((l l) (r (reverse l)) 
     (cond ((not (consp l)) result) 
      (else (setf (car l) (car r)) 
        (reving (cdr l) (cdr r))))))) 

> (defvar l '(1 2 3)) 
> (reverse-in-place l)) 
(3 2 1) 
> l 
(3 2 1) 

Answer 2

查看nreverse，它將修改列表中的列表（請參閱HyperSpec）。

按照意見，千萬注意，從規範是@Barmar提出的意見，這一點：

對於nreverse，序列可能被破壞並重新用於生產的結果。結果可能與序列相同也可能不同。具體而言，當序列是一個列表時，nreverse被允許設置屬於序列列表結構的任何cons的任何部分，car或cdr。