Reversible List in Lisp

Question

I'm trying to change the list in Lisp, but I get the error: "Error: exception C0000005 [flags 0] to 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 someone tell me what I am doing wrong? Thanks in advance!

Answer 1

Your written code is logically correct and gives the result you want:

 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) 

However, there are some problems in terms of performance. The append function creates a copy of everything except the last argument. For example, when you do (add '(1 2)' (ab) '(3 4)) , you create four new cons cells, whose cars are 1, 2, a and b. The final cdr is an existing list (3 4). This is because the append implementation looks something like this:

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

This is not exactly a Common Lisp append , because a Common Lisp append can take more than two arguments. This is close enough to show why everything except the last list is copied. Now let's see what this means in terms of your rev implementation, though:

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

This means that when you change a list, for example (1 2 3 4) , it looks like this:

 (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 copy the list (4 3). In the first line, you copy the list (4 3 2), which includes a copy (4 3). That is, you copy a copy. This is a rather wasteful use of memory.

A more general approach uses a battery variable and an auxiliary function. (Note that instead of null, I use endp , rest , first and the list * strong>, cdr , car and minus , as it gives a clear idea that we are working with lists and not with arbitrary minuses. They are almost 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) 

Using this helper function, it is 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) 

However, instead of having an external helper function, it would 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 does not guarantee tail call optimization, the do loop is also nice and clean:

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

Answer 2

In ANSI Common Lisp, you can cancel a list using the reverse function (non-destructive: selects a new list) or nreverse (rebuilds building blocks or data from an existing list to create a reverse).

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

Do not use nreverse in quoted list literals; this behavior is undefined and can behave surprisingly, as it is self-evident de facto code.

Answer 3

If you can use standard CL library functions such as append , you should use reverse (as suggested by Kaz ).

Otherwise, if this is an exercise (b / w or not), you can try the following:

 (defun rev (l) (labels ((r (todo) (if todo (multiple-value-bind (res-head res-tail) (r (cdr todo)) (if res-head (setf (cdr res-tail) (list (car todo)) res-tail (cdr res-tail)) (setq res-head (list (car todo)) res-tail res-head)) (values res-head res-tail)) (values nil nil)))) (values (rl)))) 

PS. Your specific error is not clear, contact your supplier.

Answer 4

You probably don't have enough stack space; this is the result of calling the recursive function rev , outside the tail position. The approach to converting to a tail recursive function includes introducing the accumulator, the result variable in the following:

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

The rev function will look like this:

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

Examples:

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