Обратный список 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) для повторного использования данной ячейки cons и не потерять ссылку на предыдущий 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)))) 

[править] Как уже отмечалось в комментарии, чтобы сделать это действительно на месте (и без связи с 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 разрешено устанавливать любую часть, автомобиль или cdr, любых минусов, которые являются частью структуры списка последовательности.