CLISP - Reversing a simple list

Question

I have to reverse the elements of a simple (single-dimension) list. I know there's a built-in reverse function but I can't use it for this.

Here's my attempt:

(defun LISTREVERSE (LISTR)
    (cond
        ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller
        (t (cons (LISTREVERSE (cdr LISTR)) (car LISTR))) ; move first to the end
    )
)

Output pretty close, but is wrong.

[88]> (LISTREVERSE '(0 1 2 3)) 
((((3) . 2) . 1) . 0)

So I tried to use append instead of cons:

(t (append (LISTREVERSE (cdr LISTR)) (car LISTR)))

But got this error:

*** - APPEND: A proper list must not end with 2

Any help?

Answer 1

I can give you a couple of pointers, because this looks like homework:

• The base case of the recursion is when the list is empty (null), and not when there are less than two elements in the list
• Consider defining a helper function with an extra parameter, an "accumulator" initialized in the empty list. For each element in the original list, cons it at the head of the accumulator. When the input list is empty, return the accumulator

As an aside note, the above solution is tail-recursive.

Answer 2

As a follow-up to Óscar López (and fighting the temptation to just write a different solution down):

• Using both append and length makes the posted solution just about the least efficient way of reversing a list. Check out the documentation on cons and null for some better ideas on how to implement this.
• Please, please indent properly.
• Tail recursion really is both more efficient and reasonably simple in this case. Try it if you haven't already. labels is the form you want to use to define local recursive functions.
• It may be worth your while to flip through The Little Schemer. It'll give you a better feel for recursion in general.

Answer 3

It's ok what you did. You only missed the composition of the result list.

Think about it: You have to append the 1-element list of the CAR to the end of the list of the reversed CDR:

(defun LISTREVERSE (LISTR)
    (cons
        ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller
        (t (append (LISTREVERSE (cdr LISTR)) (list (car  LISTR))))))

Answer 4

(defun listreverse (list)
  (let (result)
    (dolist (item list result)
      (push item result))))

• Don't use recursion in Common Lisp when there is a simple iterative way to reach the same goal. Common Lisp does not make any guarantees about tail recursion, and your tail recursive function invocation may not be optimized to a jump at the discretion of the compiler.
• push prepends the item to the result
• dolist has an optional third argument which is the value returned. It is evaluated when the loop is exited.