LISP - Modifications to Lists

Lisp - List Modification

In Common Lisp, lists are the quintessential data structure. Modifying lists is a common task, and Lisp provides two distinct families of functions for this: non-destructive functions that return a new, modified list, and destructive functions that modify the original list’s memory structure directly.

Understanding this distinction is one of the most critical aspects of proficient Lisp programming, as it directly impacts program correctness and performance.

Non-Destructive vs. Destructive Operations

Operation Type	Description	Key Functions
Non-Destructive (Functional Style)	These functions create and return a new list with the desired changes, leaving the original list untouched. This is safer and easier to reason about, especially in complex programs.	append, remove
Destructive (Imperative Style)	These functions modify the cons cells of the original list in-place. This can be much faster and more memory-efficient as it avoids creating new objects. By convention, their names often contain ‘n’ or ‘r’.	nconc, delete, rplaca, rplacd, push, pop

Appending to a List

Let’s compare append (non-destructive) and nconc (destructive).

main.lisp

(defparameter *list-a* '(a b c))
(defparameter *list-b* '(d e f))

;; 1. Non-destructive APPEND
(let ((new-list (append *list-a* *list-b*)))
  (format t "Result of APPEND: ~a~%" new-list)
  (format t "Original *list-a* is unchanged: ~a~%~%" *list-a*))

;; 2. Destructive NCONC
(let ((modified-list (nconc *list-a* *list-b*)))
  (format t "Result of NCONC: ~a~%" modified-list)
  (format t "Original *list-a* is NOW MODIFIED: ~a~%" *list-a*))

Output

Result of APPEND: (A B C D E F)
Original *list-a* is unchanged: (A B C)

Result of NCONC: (A B C D E F)
Original *list-a* is NOW MODIFIED: (A B C D E F)

Warning: Using nconc modifies the last cons cell of *list-a* to point to *list-b*. This is a permanent change.

Removing from a List

Similarly, remove (non-destructive) contrasts with delete (destructive).

main.lisp

;; 1. Non-destructive REMOVE
(let ((original '(a b c b d)))
  (let ((new-list (remove 'b original)))
    (format t "Result of REMOVE: ~a~%" new-list)
    (format t "Original is unchanged: ~a~%~%" original)))

;; 2. Destructive DELETE
(let ((original (list 'a 'b 'c 'b 'd)))
  ;; We must use (list ...) to create a fresh list we can safely modify.
  (let ((modified-list (delete 'b original)))
    (format t "Result of DELETE: ~a~%" modified-list)
    (format t "Original is NOW MODIFIED: ~a~%" original)))

Output

Result of REMOVE: (A C D)
Original is unchanged: (A B C B D)

Result of DELETE: (A C D)
Original is NOW MODIFIED: (A C D)

Best Practice: Only use delete on lists that you have just created and are certain are not shared anywhere else in your program.

Adding and Removing from the Front: push and pop

push and pop are efficient, destructive macros for treating a list like a stack.

main.lisp

(defparameter *stack* '(a b c))
(format t "Initial stack: ~a~%" *stack*)

;; PUSH an element onto the front
(push 'x *stack*)
(format t "After PUSH 'x: ~a~%" *stack*)

;; POP an element from the front
(let ((removed-item (pop *stack*)))
  (format t "Item popped: ~a~%" removed-item)
  (format t "After POP: ~a~%" *stack*))

Output

Initial stack: (A B C)
After PUSH 'x: (X A B C)
Item popped: X
After POP: (A B C)

Low-Level Modification: rplaca and rplacd

rplaca (replace car) and rplacd (replace cdr) are low-level destructive operators that directly change the pointers of a cons cell. Use them with extreme caution.

main.lisp

(let ((my-list (list 'a 'b 'c)))
  (format t "Original: ~a~%" my-list)

  ;; Replace the first element (the CAR of the first cons cell)
  (rplaca my-list 'x)
  (format t "After (rplaca my-list 'x): ~a~%" my-list)

  ;; Replace the rest of the list (the CDR of the first cons cell)
  (rplacd my-list '(y z))
  (format t "After (rplacd my-list '(y z)): ~a~%" my-list))

Output

Original: (A B C)
After (rplaca my-list 'x): (X B C)
After (rplacd my-list '(y z)): (X Y Z)