LISP - Reversing a Sequence

Lisp - Reversing Sequences

Reversing the order of elements in a sequence is a common task. Common Lisp provides two generic functions for this: reverse (non-destructive) and nreverse (destructive). These functions work on various sequence types, including lists, vectors, and strings.

Safe Reversal: The reverse Function

reverse creates and returns a new sequence containing the same elements as the original but in the opposite order. The original sequence is left unchanged.

Syntax

(reverse sequence)

Arguments

• sequence: A list, vector, or string to be reversed.

Return Value

A new sequence of the same type as the input, containing the elements in reverse order.

Example: Reversing Different Sequence Types

;; main.lisp
(let ((original-list '(a b c d e))
      (original-vector #(10 20 30 40 50))
      (original-string "LISP"))

  (format t "Original List: ~a~%" original-list)
  (format t "Reversed List: ~a~%~%" (reverse original-list))

  (format t "Original Vector: ~a~%" original-vector)
  (format t "Reversed Vector: ~a~%~%" (reverse original-vector))

  (format t "Original String: ~a~%" original-string)
  (format t "Reversed String: ~a~%~%" (reverse original-string))

  (format t "Original list is unchanged: ~a~%" original-list))

Output

Original List: (A B C D E)
Reversed List: (E D C B A)

Original Vector: #(10 20 30 40 50)
Reversed Vector: #(50 40 30 20 10)

Original String: "LISP"
Reversed String: "PSIL"

Original list is unchanged: (A B C D E)

Destructive Reversal: The nreverse Function

nreverse reverses a sequence by modifying it in place. This can be more memory-efficient but must be used with extreme caution as it destroys the original sequence structure.

Syntax

(nreverse sequence)

Behavior and Best Practices

• For Lists: nreverse is highly efficient. It works by changing the cdr of each cons cell to point to the previous cell. The original list structure becomes invalid.
• For Vectors: nreverse modifies the vector in place.
• For Strings: You should not use nreverse on strings. Strings are specified as immutable, and attempting to modify one leads to an error in modern Lisp implementations.
• The Golden Rule: Only use nreverse on a sequence that you have just created and will not be referenced anywhere else. A classic idiom is to build a list using push (which is fast) and then nreverse it at the end to get the intended order.

Example: The Classic push/nreverse Idiom

;; main.lisp
(let ((result-list nil)) ; Start with an empty list

  ;; Build the list by pushing elements. This is fast but builds the list backwards.
  (dotimes (i 5)
    (push (* i i) result-list))

  (format t "List after pushing (reversed order): ~a~%" result-list)

  ;; Now, use nreverse to correct the order. This is safe because `result-list` is temporary.
  (let ((final-list (nreverse result-list)))
    (format t "Final list after nreverse: ~a~%" final-list)))

Output

List after pushing (reversed order): (16 9 4 1 0)
Final list after nreverse: (0 1 4 9 16)

When to Choose reverse vs. nreverse

• Use reverse (Safe): This should be your default choice. It follows functional programming principles (no side effects) and prevents a whole class of bugs. The performance cost is usually negligible.
• Use nreverse (Optimized): Use this only when you have identified a performance bottleneck in a hot loop and can prove that the sequence being reversed is temporary and not shared. The push/nreverse idiom is the most common and accepted use case.

Testing and Verification

To truly understand the destructive nature of nreverse, try running this code:

(let ((my-list '(1 2 3)))
  (print (nreverse my-list))
  ;; Now inspect my-list. Its structure has been altered!
  (print my-list))

Potential Output

(3 2 1)
(1) ; The original binding now points to a corrupted list fragment!