Is the book answer-sheet wrong about this multiple recursion with car/cdr in Common Lisp?

user_9113679 0
Viewed 56

I am trying to learn Common Lisp with the book Common Lisp: A gentle introduction to Symbolic Computation. In addition, I am using SBCL, Emacs, and Slime.

In the middle of chapter 8, the author presents recursion on trees. He showcases this concept with a function on trees that inserts the symbol 'q in all non-list elements of the tree:

enter image description here

I did the same in my environment:

(defun atoms-to-q (xs)
  (cond ((null xs) nil)
        ((atom xs) 'q)
        (t (cons (atoms-to-q (car xs))
                 (atoms-to-q (cdr xs))))))

And I got the same results:

CL-USER> (atoms-to-q '(a . b))
(Q . Q)
CL-USER> (atoms-to-q '(hark (harold the angel) sings))
(Q (Q Q Q) Q)

Then the book asks:

enter image description here

The same book provides a great aswer sheet. Which shows as an answer for this specific question:

8.38. If the first COND clause is omitted, the NILs at the end of cons cell chains will also be converted to Qs. So (ATOMS-TO-Q ’(A (B) C)) will return (A (B . Q) C . Q)

Now we reach the point of confusion for me. In my environment I removed the first clause with:

(defun atoms-to-q-no-null (xs)
  (cond ((atom xs) 'q)
        (t (cons (atoms-to-q (car xs))
                 (atoms-to-q (cdr xs))))))

And after running the function with inputs suggested on the book's answer sheet I get a different result:

CL-USER> (atoms-to-q-no-null '(a (b) c))
(Q (Q) Q)
tree common-lisp
1 Answers

Unfortunately, while coping and yaking I forgot to change the recursive calls on atoms-to-q-no-null. I realized this error while preparing this question for stackoverflow.

Since I had already written some part of the question, I thought it would be better to answer it and make the effort useful for other people.

After fixing the recursive calls of the function:

(defun atoms-to-q-no-null (xs)
  (cond ((atom xs) 'q)
        (t (cons (atoms-to-q-no-null (car xs))
                 (atoms-to-q-no-null (cdr xs))))))

I got the same results:

CL-USER> (atoms-to-q-no-null '(a (b) c))

(Q (Q . Q) Q . Q)

This is a very interesting and well-written book, by the way.

user_91136790
Related