reversing list in Lisp

Question

I'm trying to reverse a list in Lisp, but I get the error: " Error: Exception C0000005 [flags 0] at 20303FF3 {Offset 25 inside #} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 "

My code is as follows:

(defun rev (l)
    (cond
        ((null l) '())
        (T (append (rev (cdr l)) (list (car l)))))) 

Can anyone tell me what am I doing wrong? Thanks in advance!

Answer 1

Your code as written is logically correct and produces the result that you'd want it to:

CL-USER> (defun rev (l)
           (cond
             ((null l) '())
             (T (append (rev (cdr l)) (list (car l)))))) 
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)

That said, there are some issues with it in terms of performance. The append function produces a copy of all but its final argument. E.g., when you do (append '(1 2) '(a b) '(3 4)), you're creating a four new cons cells, whose cars are 1, 2, a, and b. The cdr of the final one is the existing list (3 4). That's because the implementation of append is something like this:

(defun append (l1 l2)
  (if (null l1)
      l2
      (cons (first l1)
            (append (rest l1)
                    l2))))

That's not exactly Common Lisp's append, because Common Lisp's append can take more than two arguments. It's close enough to demonstrate why all but the last list is copied, though. Now look at what that means in terms of your implementation of rev, though:

(defun rev (l)
  (cond
    ((null l) '())
    (T (append (rev (cdr l)) (list (car l)))))) 

This means that when you're reversing a list like (1 2 3 4), it's like you're:

(append '(4 3 2) '(1))              ; as a result of    (1)
(append (append '(4 3) '(2)) '(1))  ; and so on...      (2)

Now, in line (2), you're copying the list (4 3). In line one, you're copying the list (4 3 2) which includes a copy of (4 3). That is, you're copying a copy. That's a pretty wasteful use of memory.

A more common approach uses an accumulator variable and a helper function. (Note that I use endp, rest, first, and list* instead of null, cdr, car, and cons, since it makes it clearer that we're working with lists, not arbitrary cons-trees. They're pretty much the same (but there are a few differences).)

(defun rev-helper (list reversed)
  "A helper function for reversing a list.  Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED.  (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
  (if (endp list)
      reversed
      (rev-helper (rest list)
                  (list* (first list)
                         reversed))))

CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)

With this helper function, it's easy to define rev:

(defun rev (list)
  "Returns a new list containing the elements of LIST in reverse
order."
  (rev-helper list '()))

CL-USER> (rev '(1 2 3))
(3 2 1)

That said, rather than having an external helper function, it would probably be more common to use labels to define a local helper function:

(defun rev (list)
  (labels ((rev-helper (list reversed)
             #| ... |#))
    (rev-helper list '())))

Or, since Common Lisp isn't guaranteed to optimize tail calls, a do loop is nice and clean here too:

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))

Answer 2

In ANSI Common Lisp, you can reverse a list using the reverse function (nondestructive: allocates a new list), or nreverse (rearranges the building blocks or data of the existing list to produce the reversed one).

> (reverse '(1 2 3))
(3 2 1)

Don't use nreverse on quoted list literals; it is undefined behavior and may behave in surprising ways, since it is de facto self-modifying code.