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!

Solution 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)))

Solution 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.

Solution 3

You've likely run out of stack space; this is the consequence of calling a recursive function, rev, outside of tail position. The approach to converting to a tail-recursive function involves introducing an accumulator, the variable result in the following:

(defun reving (list result)
  (cond ((consp list) (reving (cdr list) (cons (car list) result)))
        ((null list) result)
        (t (cons list result))))

You rev function then becomes:

(define rev (list) (reving list '()))

Examples:

* (reving '(1 2 3) '())
(3 2 1)
* (reving '(1 2 . 3) '())
(3 2 1)

* (reving '1 '())
(1)

Comments

[Nelly]

I'm using it as the "otherwise" branch, after that all the conditions were checked..

[Renzo]

The function for Common Lisp is correct. Which lisp are you using? elisp?

[Nelly]

LispWorks Personal Edition 6.1.1

[uselpa]

Works fine for me (LW PE 6.1.1 on Mac). How are you calling rev?

[uselpa]

@NathanHughes Only if the first element is a (sub-)list.

[cybevnm]

Are you running lisp on MS Windows ? C0000005 is exception code for Access Violation - Segmentation Violation in MS Windows world. Don't know what causes it in your case though. Maybe debugging level increase / optimization level decrease can help pinpoint the issue, if possible on your implementation...

[Nelly]

Sorry, I do not understand what "consp" means here.. can you explain a bit?

[Nelly]

Thank you a lot! Your answer really helped me.

[GoZoner]

conspis the type predicate for a 'cons cell'. Every proper list is a sequence of cons cells ending in a nil. If you try (cons 1 (cons 2 nil)) you'll get a list of (1 2). In my reving code above, if list is a cons then push the car onto result and recurse on the rest of the list (via cdr).

[Nelly]

I still have a question.. what if there are sub-lists in the initial list? I tried to modify a bit you code, using "mapcar" function in "rev", but I get the result "NIL" ... can you give me a suggestion?

[Joshua Taylor]

@Nelly I'm not sure at all what you mean, and certainly can't guess what problem you ran into just by "I get the result NIL". You don't need any modification for lists that have lists as elements. When you reverse ((1 2) (3 4)) you get ((3 4) (1 2)), a new list with the same elements, but in reverse order.

[Nelly]

I got your point, and you're right. But, I want to reverse also the elements from the sub-lists. So, that's why I wrote something like: " ( mapcar #'rev-helper list '()) " in "rev", and for instance, calling " (rev '(1 2 '(3 4) 5 '(6 7))) " gives me the result " NIL" ..

[Joshua Taylor]

@Nelly I'm on mobile at the moment, so I can't provide a full response. First, you'll not want to put more quotes in the inner lists. That is, do '(1 2 (3 4)) not '(1 2 '(3 4)) [I can provide a link to another question about that]. Second, there's another recent question about reversing recursively that probably does what you want. Third, in your attempt, your using mapcar incorrectly. Mapcar calls the function arguments from each list. E.g., (mapcar '+ (1 2) (3 4)) returns (4 6), because it calls + with 1 and 3, and then with 2 and 4. If you do (mapcar #'rev-helper list '()), the second

[Joshua Taylor]

list is empty, of course you get the empty list back. Just like (mapcar '+ (1 2) '()) would return (). Finally, if you wanted to ask about reversing a list and all of its sublists, you should have mentioned that in the question; we can't predict the requirements of the problem at hand, after all.

[Nelly]

You're right about the quotes. Also, seems like I misunderstand the effect of "mapcar", since I notice that I do not know how to use it properly. And, sorry about that I did not mention, the whole problem from the beginning. I just thought that I will figure out by myself how to do the rest of the problem.

[Paul]

Functions reverse and nreverse became part of emacs at version 18.