-1

I am attempting to write a function that calls a list recursively and reverses its order. However I need to make the function operate every other recursive level and I am attempting to pass boolean arguments to use as a flag. I am very new to Lisp and keep getting an Undefined function B error.

(defun revList (L b)
  (cond ((null L) nil)
        ((b T)
         (append (revList (cdr L nil))
                 (list (car L))))
        ((b nil)
         (append (revList (cdr L T))
                 (list (car L))))))

(print (revlist '(1 (2 3) (4 (5 6)) (7 (8 (9 10)))) t))
ad absurdum
  • 19,498
  • 5
  • 37
  • 60
Nick Reck
  • 7
  • 1
  • 2
    First step: indent your code properly so it is readable. Lisp reads 'S-Expressions', which by default are (function variables). So your expression (b T), lisp reads as "apply function b to variable T", but, there is no function named 'b'. – Halbert Nov 15 '21 at 03:48
  • 2
    Second: COND is already checking for a boolean value. You don't need some other function. – Halbert Nov 15 '21 at 03:52
  • 1
    "_make the function operate every other recursive level_" -- what is the goal here? Example inputs with expected outputs would be helpful. Should `(revList '(1 2 3 4) t)` --> `(4 3 2 1)` or `(2 4 3 1)`? Should `(revList '(1 2 3 (a b c (4 5 6))) t)` --> `((a b c (6 5 4)) 3 2 1)`? That is, do you want to reverse only on alternate _recursive calls_, or do you want to reverse _alternate levels of nesting_? – ad absurdum Nov 15 '21 at 06:29
  • In a REPL, you don't have to say `(print (revlist '(1 (2 3) (4 (5 6)) (7 (8 (9 10)))) t))`. You only have to say `(revlist '(1 (2 3) (4 (5 6)) (7 (8 (9 10)))) t)`, and the REPL will print it for you. – Francis King Nov 15 '21 at 08:47
  • Does this answer your question? [How to store a function in a variable in Lisp and use it](https://stackoverflow.com/questions/19375270/how-to-store-a-function-in-a-variable-in-lisp-and-use-it) – Kaz Nov 18 '21 at 01:12

1 Answers1

4

The first problem, and the reason for the reported error message Undefined function B is that some test forms in the cond form are attempting to call a function b which has not been defined. In a cond form the test forms are evaluated, and the result is used to determine which branch should be used. When (b T) or (b nil) are evaluated, it is expected that b is a function or macro. Instead you should use an expression which evaluates to either a true value or nil here.

There is another problem of misplaced parentheses around a couple of calls to cdr: (cdr L nil) and (cdr L T).

Once these problems are fixed, the code looks like this:

(defun revList (L b)
  (cond ((null L) nil)
        (b
         (append (revList (cdr L) nil)
                 (list (car L))))
        (t
         (append (revList (cdr L) t)
                 (list (car L))))))

I'm going to rewrite the above function using some better names to make things a bit more clear. Note that the idiomatic way to introduce an else clause into a cond form is to use t as the test form in the final clause:

(defun rev-helper-1 (xs reverse-p)
  (cond ((null xs) nil)
        (reverse-p
         (append (rev-helper-1 (cdr xs) nil)
                 (list (car xs))))
        (t
         (append (rev-helper-1 (cdr xs) t)
                 (list (car xs))))))

This code compiles and runs, but probably does not do what is expected. When reverse-p is true the code does exactly the same thing as when it is false, except that the sense of reverse-p is flipped. So the code always reverses its input:

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

Further, this code does not descend into nested lists:

CL-USER> (rev-helper-1 '(1 2 3 4 (a b c d (5 6 7 8))) nil)
((A B C D (5 6 7 8)) 4 3 2 1)

It isn't entirely clear from the OP post whether the desired goal is to reverse list elements on alternate recursive calls, or to reverse list elements in alternate levels of nesting. I suspect that the second goal is the correct one.

Reversing on Alternate Recursive Calls

To reverse list elements on alternating recursive calls, the code needs to cons the first element of the list back onto the front of the "reversed" remainder of the list whenever it is in a non-reversing call. In this way, every other element will be moved to the back of the list, and those moved to the back will be in reverse order in the final list.

(defun rev-helper-2 (xs reverse-p)
  (cond ((null xs) nil)
        (reverse-p
         (append (rev-helper-2 (cdr xs) nil)
                 (list (car xs))))
        (t
         (cons (car xs)
               (rev-helper-2 (cdr xs) t)))))
CL-USER> (rev-helper-2 '(1 2 3 4) t)
(2 4 3 1)

Reversing in Alternate Levels of Nesting

To reverse in alternate levels of nesting, the code needs distinguish between atoms and lists in the input.

If the first element of a list is an atom, and if the current level is a reversing level, then the first element is wrapped in a list and appended to the result of reversing the rest of the level. Otherwise, if the first element is an atom, and the current level is not a reversing level, then the first element is consed onto the front of "reversing" the rest of the level. In this second case "reversing" the rest of the level will not change the ordering of elements at this level, because reverse-p will be false for non-reversing levels; but the code still needs to walk over the list to see if any elements at this level are lists which require further processing.

Otherwise, the first element is a list. If the current level is a reversing level, then the first element must be "reversed", i.e., processed by the reversing function, then wrapped in a list and appended to the end of reversing the rest of the list. Otherwise the current level is not a reversing level, so the first element must be processed by the reversing function and consed onto the front of "reversing" the rest of the list.

(defun rev-helper-3 (xs reverse-p)
  (cond ((null xs) nil)
        ((atom (car xs))
         (if reverse-p
             (append (rev-helper-3 (cdr xs) t)
                     (list (car xs)))
             (cons (car xs)
                   (rev-helper-3 (cdr xs) nil))))
        (reverse-p
         (append (rev-helper-3 (cdr xs) t)
                 (list (rev-helper-3 (car xs) nil))))
        (t
         (cons (rev-helper-3 (car xs) t)
               (rev-helper-3 (cdr xs) nil)))))

Using a let form to bind the results of (car xs) and (cdr xs) to a couple of descriptive identifiers reduces the number of calls to car and cdr and makes this a bit easier to read:

(defun rev-helper-4 (xs reverse-p)
  (if (null xs) nil
      (let ((first (car xs))
            (rest (cdr xs)))
        (cond ((atom first)
               (if reverse-p
                   (append (rev-helper-4 rest t)
                           (list first))
                   (cons first
                         (rev-helper-4 rest nil))))
              (reverse-p
               (append (rev-helper-4 rest t)
                       (list (rev-helper-4 first nil))))
              (t
               (cons (rev-helper-4 first t)
                     (rev-helper-4 rest nil)))))))

Let's write a convenience function to make it nicer to call rev-helper-4:

(defun rev-alt (xss)
  (rev-helper-4 xss t))
CL-USER> (rev-alt '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev-alt '(1 2 3 4 (a b c d)))
((A B C D) 4 3 2 1)
CL-USER> (rev-alt '(1 2 3 4 (a b c d (5 6 7 8))))
((A B C D (8 7 6 5)) 4 3 2 1)
CL-USER> (rev-alt '(1 (2 3) (4 (5 6)) (7 (8 (9 10)))))
((7 ((9 10) 8)) (4 (6 5)) (2 3) 1)
ad absurdum
  • 19,498
  • 5
  • 37
  • 60