CODEWITHSUNDEEP
lisp
linkyndy
linkyndy

Reputation: 17928

Reverse LISP list in place

I would like to write a function that reverses the elements of a list, but it should happen in place (that is, don't create a new reversed list).

Something like:

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

What flags should I follow to achieve this?

Upvotes: 1

Views: 680

Answers (2)

GoZoner
GoZoner

Reputation: 70245

It's not difficult to implement this (ignoring fault cases). The keys are to use (setf cdr) to reuse a given cons cell and not to lose the reference to the prior 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))))

[edit] As mentioned in a comment, to do this truly in-place (and w/o regard to 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)

Upvotes: 1

Jeff Foster
Jeff Foster

Reputation: 44746

Have a look at nreverse which will modify the list in place (see HyperSpec).

As per the comments, do note the comments that @Barmar made and this bit from the spec:

For nreverse, sequence might be destroyed and re-used to produce the result. The result might or might not be identical to sequence. Specifically, when sequence is a list, nreverse is permitted to setf any part, car or cdr, of any cons that is part of the list structure of sequence.

Upvotes: 8

Related Questions