《ANSI Common Lisp》第二章习题

1. Describe what happens when the following expressions are evaluated:

   (a) (+ (- 5 1) (+ 3 7))
   (b) (list 1 (+ 2 3))
   (c) (if (listp 1) (+ 1 2) (+ 3 4))
   (d) (list (and (listp 3) t) (+ 1 2))
   

   My answer:

   (a) 14

   (b) (1 5)

   (c) 7

   (d) (NIL 3)

2. Give three distinct cons expressions that return (a b c).

   My answer:

   (cons 'a '(b c))
   (cons 'a (cons 'b '(c)))
   (cons 'a (cons 'b (cons 'c nil)))
   

3. Using car and cdr,define a function to return the fourth element of a list.

   My answer:

   (defun fourth (lst)
     (if (listp lst)
       (car (cdr (cdr (cdr lst))))))
   

4. Define a function that takes two arguments and returns the greater of the two.

   My answer:

   (defun greater (a b)
     (if (equal (type-of a)
                (type-of b))
         (cond ((typep a 'number) (if (> a b) a b)
               ((typep a 'character) (if (char> a b) a b))
               ((typep a 'string) (if (string> a b) a b))
               (t nil)))
         nil))
   

5. What do hese functions do?

   (a)

   (defun enigma (x)
     (and (not (null x))
          (or  (null (car x))
               (enigma (cdr x)))))
   

   (b)

   (defun mystery (x y)
     (if (null y)
         nil
         (if (eql (car y) x)
             0
             (let ((z (mystery x (cdr y))))
               (and z (+ z 1))))))
   

   My answer:

   (a) 该函数用于判断一个非空的list中是否含有 NIL 元素.

   (b) 判断y中是否有元素和x相等(同一个对象)，若无则返回NIL，若有则返回该元素在y中的索引(以0为初始值).

6. What could occur in place of the x in each of the following exchanges?

   (a) > (car (x (cdr '(a (b c) d))))
       B
   (b) > (x 13 (/ 1 0))
       13
   (c) > (x #'list 1 nil)
       (1)
   

   My answer:

   (a) cdr.

   (b) or.

   (c) apply.

7. Using only operators introduced in this Chapter, define a function that takes a list as an argument and returns true if one of its elements is a list.

   My answer:

   (defun have-list-member (lst)
     (if (null lst)
         nil
         (if (listp (car lst))
             t
             (have-list-member (cdr lst)))))
   

   注：本章出现的操作符有：

   + / - quote list cons car cdr third listp null not if and or defun > eql read format let defparameter defconstant setf remove do dolist progn function apply funcall lambda typep
   

8. Give iterative and recursive definitions of a function that

   (a) takes a positive integer and prints that many dots.

   (b) takes a list and returns the number of times the symblo a occurs in it.

   My answer:

   (a) dot-plot

   • Iteractive version

     (defun dot-plot-iter (n)
       (do ((n n (- n 1)))
           ((= n 0) 'done)
         (format t ".")))
     

   • Recursive version

     (defun dot-plot-rec (n)
       (if (= n 0)
           'done
           (progn
             (format t ".")
             (dot-plot-rec (- n 1)))))
     

   (b) times-of-a

   • Iteractive version

     (defun bfs (lst)                     ;广度优先遍历，得到lst的所有树叶节点的列表
       (let ((stack (list lst))           ;遍历所需栈
             (leaves nil))                ;存放树叶节点的列表
         (do ()
             ((null stack) leaves)        ;当栈空时，遍历结束
           (let ((now (pop stack)))       ;将栈顶节点出栈
             (if (listp now)              ;若出栈节点不为树叶节点时，将其子树入栈
                 (progn (push (car now) stack)
                        (if (not (null (cdr now)))   ;这里要判断cdr是否为nil，否则将其入栈后
                            (push (cdr now) stack))) ;listp对其判断的结果为真，导致无穷递归
                 (push now leaves))))))   ;若出栈节点为树叶节点，将其放入leaves列表中
     
     (defun times-of-a-iter (lst)
       (let ((leaves (bfs lst))
             (times 0))
         (dolist (obj lst)
           (if (equal 'a obj)
               (setf times (+ times 1))))
         times))
     

   • Recursive version

     (defun times-of-a-rec (lst)
       (if (null lst)
            0
           (let ((now (car lst)))
             (+ (if (listp now)
                    (times-of-a-rec now)
                    (if (equal now 'a) 1 0))
                (times-of-a-rec (cdr lst))))))
     

1. A friend is trying to write a function that returns the sum of all the non-nil elements in a list. He has written two versions of this function, and neither of them work.Explain what's wrong with each, and give a correct version:

   (a)

   (defun summit (lst)
     (remove nil lst)
     (apply #'+ lst))
   

   (b)

   (defun summit (lst)
     (let ((x (car lst)))
       (if (null x)
           (summit (cdr lst))
           (+ x (summit (cdr lst))))))
   

   My answer:

   (a) remove是没有副作用(side-effect)的，所以lst中的 nil 元素还在 lst中，正确的代码应为

   (defun summit (lst)
     (apply #‘+ (remove nil lst)))
   

   (b) 没有递归终止条件，正确的代码应为：

   (defun summit (lst)
     (if (null lst)
         0
         (let ((x (car lst)))
           (if (null x)
               (summit (cdr lst))
               (+ x (summit (cdr lst)))))))