《ANSI Common Lisp》第三章习题

1. Show the following lists in box notation:

   (a) (a b (c d))
   (b) (a (b (c (d))))
   (c) (((a b) c) d)
   (d) (a (b . c) . d)
   

   My answer:

   (a) (a . (b . ((C . (D . NIL)) . NIL)))

   (b) (a . ((B . ((C . ((D . NIL) . NIL)) . NIL)) . NIL))

   (c) (((A . (B . NIL)) . (C . NIL)) . (D . NIL))

2. Write a version of union that preserves the order of the elements in the original lists:

   > (new-union '(a b c) '(b a d))
   (A B C D)
   

   My answer:

   (defun new-union (first second)
     (dolist (obj second)
       (if (not (member obj first))
           (append first (list obj)))))
   

3. Define a function that takes a list and returns a list indicating the number of times each (eql) element appears, sorted from most common element to least common:

   > (occurrences '(a b a d a c d c a))
   ((A . 4) (C . 2) (D . 2) (B . 1))
   

   My answer:

   (defun occurrence (lst)
     (let ((result nil))
       (dolist (obj lst)
         (if (null (assoc obj result))
         (push (cons obj 1) result)
         (incf (cdr (assoc obj result)))
       ))
       (sort result #'(lambda (a b) (if (> (cdr a) (cdr b)) t nil)))))
   

4. Why does (member '(a) '((a) (b))) return nil?

   My answer:

   因为每次产生cons调用时系统都会分配新的对象，所以'(a)和'((a) (b))中的第一个元素虽然具有同样的值，但却不是同一个对象，而member函数使用的判定函数是eql。

5. Suppose the function pos+ takes a list and returns a list of each element plus its position:

   > (pos+ '(7 5 1 4))
   

   Define this function using (a) recursion, (b) iteration, (c) mapcar.

   My answer:

   (a) Recursive version

   (defun rec-pos-plus (lst pos) 
     (if (not (null lst))
         (progn
       (incf (car lst) pos)
       (rec-pos-plus (cdr lst) (1+ pos)))))
   
   (defun rec-pos+ (lst)
     (rec-pos-plus lst 0)
     lst)
   

   (b) Iterative version

   (defun iter-pos+ (lst)
     (do ((i 0 (+ i 1)))
         ((= i (length lst)) lst)
       (incf (nth i lst) i)
       ))
   

   (c) Version using mapcar

   (defun pos+ (lst)
     (mapcar #'(lambda (x) (incf x (position x lst)))
         lst))
   

6. After yeas of deliiberation, a government commission has decided that lists should be represented by using the cdr to point to the first element and the car to point to the rest of the list. Define the government versions of the following functions:

   (a) cons
   (b) list
   (c) length (for lists)
   (d) member (for lists; no keywords)
   

   My answer:

   (a) cons

   (defun cons (x y)
     (let ((result '(nil . nil)))
       (setf (cdr result) x)
       (setf (car result) y)))
   

   (b) list

   (defun list (&rest arg)
     arg)
   

   (c) length (for lists)

   (defun length (lst)
     (if (null lst)
         0
         (+ 1 (length (car lst)))))
   

   (d) member (for lists; no keywords)

   (defun member (element list)
     (cond ((null list) nil)
           ((eql element (cdr list)) list)
           (t (member element (car list)))))
   

7. Modify the program in Figure 3.6 to use fewer cons cells. (Hing: Use dottedlists.)

   My answer:

   (defun n-elts (elt n)
     (if (> n 1)
         (cons n elt)
         elt))
   
   (defun compr (elt n lst)
     (if (null lst)
         (list (n-elts elt n))
         (let ((next (car lst)))
       (if (eql next elt)
           (compr elt (+ n 1) (cdr lst))
           (cons (n-elts elt n)
             (compr next 1 (cdr lst)))))))
   
   (defun compress (x)
     (if (consp x)
         (compr (car x) 1 (cdr x))
         x))
   

8. Define a function that takes a list and prints it in dot natation:

   > (showdots '(a b c))
   (A . (B . (C . NIL)))
   NIL
   

   My answer:

   (defun showdots (list)
   (cond ((null list) nil)
     ((consp list) (progn
            (format t "(")
            (showdots (car list))
            (format t " . ")
            (if (null (cdr list))
                (format t "NIL")
                (showdots (cdr list)))
            (format t ")")
            ))
     (t (format t "~a" list))))
   

9. Write a program to find the longest finite path through a network represented as in Section 3.15. The network may contain cycles.

   My answer(对shortest-path的改写):

   (defun new-paths (path node net)
     (mapcar #'(lambda (n) 
                  (if (not (member n path)) ;判断下一层节点是否包含在路径中以削除环的影响
                      (cons n path)))
             (cdr (assoc node net))))
   
   (defun bfs (end quene net)
     (if (null quene)
         nil
         (let ((path (car quene)))
           (let ((node (car path)))
             (if (eql node end)
                 (reverse path)
                 (bfs end
                      (sort (append (cdr quene) ;排序以保证最长的路径在队列最前方
                                    (new-paths path node net))
                            #'>
                            :key #'length)
                      net))))))
   
   (defun longest-path (start end net)
     (bfs end (list (list start)) net))
   

= =写个题比拿半生不熟的英文来记笔记还累……