Is the book's answer-sheet wrong about this "flatten the nested list" problem?

user_9113679 0
Viewed 51

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 Chapter 8, the author presents the concept of recursion. More specifically, he shows cad/cdr recursion on trees. One of the exercises about this topic is how to flat a nested list:

enter image description here

The odd thing appears in the answer-sheet showing this as the correct answer:

enter image description here

The book's answer-sheet solution does not generate the expected result with the example provided on the question under my environment.

(defun flatten-book (tree)
  (cond ((atom tree) (list tree))
         (t (append (flatten-book (car tree))
                    (flatten-book (cdr tree))))))

It is full of NILs and it should not be. Thus, I get on my REPL:

CL-USER> (flatten-book '((A B (R)) A C (A D ((A (B)) R) A)))
(A B R NIL NIL A C A D A B NIL NIL R NIL A NIL NIL)

In order to get the expected result I need to change the approach inserting a null clause with:

(defun my-flatten (tree)
  (cond ((null tree) nil)
        ((atom tree) (list tree))
        (t (append (my-flatten (car tree))
                   (my-flatten (cdr tree))))))

This returns the correct answer:

CL-USER> (my-flatten '((A B (R)) A C (A D ((A (B)) R) A)))

(A B R A C A D A B R A)

So far, I am enjoying the book a lot. And it seems to be a classic among Common Lispers.

Is this an error in the book's answer-sheet? Did I miss something? Maybe a historical change? Maybe something related to a different compiler?

tree recursion common-lisp
1 Answers

The book is wrong.

With this small change however, the answer from the book works again:

(defun flatten (tree)
  (cond ((null tree) tree) ;; this case was forgotten by the book!
        ((atom tree) (list tree))
        (t (append (flatten (car tree))
                   (flatten (cdr tree))))))
user_96900900
Related