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?

Partridge

The use of LENGTH is not a good idea. It defeats the purpose of lists of linked cons cells. LENGTH traverse the whole list to determine the length. – Prospect

The APPEND error is a bit cryptic, but it means that the last of the arguments is not a list, but the number 2. – Prospect

Unless I'm mistaken, your append version should work as long as you make the last argument into a list. – Ap

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.

Midkiff

I tried to do it with base case null, But then I get ((((NIL 3) 2) 1) 0). Also I know tail-recursion is needed in lisp for it to run fast but I don't want to overdo it when the specifications say 'a function'. – Partridge

@Partridge you're getting those weird results precisely because you're not using a parameter as an accumulator to hold your results. In this case the simplest solution also happens to be the efficient one: use the accumulator - incidentally it's a tail recursion, you won't be "overdoing" it. – Cootie

I got it working without the tail recursion, but only cuz its a single-dimension list (with more dimensions I can see the need). null was the base case though. thanks for that hint – Partridge

@Partridge great! sorry I couldn't give you a straight answer, it's against the policy of the site to do people's homework. Anyway, if this answer was helpful for you, please consider accepting it (click the check mark to its left) – Cootie

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.

Phylum

Those indentation rules are stupid. +1 for the other parts of the answer. – Strongminded

@SethCarnegie - I deduce that you are a C++ or Java programmer whose editor doesn't do paren-matching. – Phylum

The indentation system given at that page are followed by the vast majority of the Lisp programming world. I suspect you glanced at the very first example and didn't see the sentence above it which says "do not write like this:". – Wiggly

Common Lisp compilers are not required to support tail recursion. It's an optimization in Lisp, not a semantic requirement like in Scheme. – Wiggly

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

Kristie

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.

Eckard