LISP - Reversing a List

Lisp - Reversing a List

Reversing the order of elements in a list is a common task. Common Lisp provides two functions for this purpose: reverse and nreverse. They achieve the same result but have a crucial difference in how they operate: one is safe and non-destructive, while the other is fast but destructive. Choosing the right one is a matter of balancing safety and performance.

The Safe Method: reverse

The reverse function creates and returns a new list containing the elements of the original list in reverse order. The original list is left completely unchanged.

Syntax

(reverse sequence)

Example

(let ((original-list '(a b c d e)))
  (format t "Original List: ~a~%" original-list)

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

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

Output

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

When to use reverse: This should be your default choice. It’s safe and prevents unexpected side effects, which is a core principle of good functional programming. Use it unless you have a proven performance bottleneck.

The Destructive Method: nreverse

The nreverse function (the ‘n’ stands for ‘non-consing’ or ‘destructive’) reuses the memory of the original list to create the reversed list. This is faster and avoids allocating new memory, but it destroys the original list. After calling nreverse, the variable pointing to the original list is no longer valid and should not be used.

Syntax

(nreverse sequence)

Example

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

  ; Destructively reverse the list. We MUST capture the return value.
  (setf my-list (nreverse my-list))

  (format t "List after nreverse: ~a~%" my-list))

Output

Original List: (A B C D E)
List after nreverse: (E D C B A)

When to use nreverse: Use it in performance-critical code where you know the original list will not be needed again. It’s common to build up a list (which is efficient to do in forward order) and then nreverse it at the end to get the desired order, avoiding garbage collection overhead.

A Word of Caution: The Dangers of nreverse

The destructive nature of nreverse can lead to surprising bugs if you’re not careful. Consider this scenario where two variables point to the same list data:

(let* ((list-a (list 1 2 3))
       (list-b list-a)) ; list-b is an alias, not a copy!

  (format t "Before: list-a = ~a, list-b = ~a~%" list-a list-b)

  (setf list-a (nreverse list-a))

  (format t "After:  list-a = ~a, list-b = ~a~%" list-a list-b))

Potential Output

Before: list-a = (1 2 3), list-b = (1 2 3)
After:  list-a = (3 2 1), list-b = (1)

Because nreverse modified the underlying structure, list-b is now pointing to a fragment of the old list and is effectively broken. This kind of bug can be very hard to track down.

Summary and Best Practices

Characteristic	reverse	nreverse
Safety	Safe, non-destructive.	Unsafe, destructive.
Performance	Slower, allocates new memory.	Faster, reuses existing memory.
Original List	Remains intact.	Is destroyed and should not be used.
Use Case	Default choice for most situations.	Performance-critical code where the original list is discarded.

Golden Rule: When in doubt, use reverse. Only optimize to nreverse when you have measured a performance problem and understand the consequences.