《ANSI COMMON LISP》第三章 习题

LISP

---

1. 用箱子表示法表示以下列表：
最后一个(a (b . c) d)。

这个答案有问题，最后的d前面的指针应该指向一个cons对象，cons对象的car指向d，cdr指向NIL。

2. 写一个保留原本列表中元素顺序的union版本：

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

(defun new_union (x y)
    (let ((rx (reverse x)))
        (dolist (mb y)
            (if (not (member mb x))
                (push mb rx)))
        (reverse rx)))

3. 定义一个函数，接受一个列表并返回一个列表，指出相等元素出现的次数，并由由最常见至最少见的排序：

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

(defun occurrences (x)
    (if (not (consp x))
        nil
        (let ((out nil))
            (dolist (obj x)   轮询列表的每个元素
                (let ((alist (assoc obj out)))   从输出关联列表中寻找是否有相应的key
                    (if alist  如果存在则自增相应关联列表的value
                        (incf (cdr alist))
                        (push (cons obj 1) out)))) 否则创建新的关联列表并压入到输出列表中
            (sort out #'> :key #'cdr)))) 使用sort排序

回顾

多数CL函数接受一个或多个 关键字参数。 这些关键字参数不是把对应的参数放在特定的位置作匹配，而是在函数调用中用特殊标签，称为关键字，来匹配。

• :test参数
  传入某个函数作为:test参数，那么那个函数就会被用来比较是否相等，而不是eql。

• :key参数
  借由提供这个参数，你可以在比较之前，指定一个函数运用在每个元素。

4. 为什么(member '(a) '((a) (b)))返回nil？
因为member默认采用eql来比较对象，很明显'(a)和((a) (b))里面的不是一个对象。如果(member '(a) '((a) (b)) :test #'equal)则返回((A) (B))。

5. 假设函数pos+接受一个列表并返回把每个元素加上自己的位置的列表：

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

(defun pos+ (list) 命令式编程 我自己做的
    (let ((len (length list)))
        (if (zerop len)
            nil
            (let ((output nil) (idx 0))
                (dolist (obj list)
                    (progn
                        (push (+ obj idx) output)
                        (setf idx (+ idx 1))))
                (reverse output)))))  
(defun pos+ (list) 函数式编程，答案里面代码最短的
    (let ((i -1))
        (mapcar #'(lambda (x) (+ x (incf i))) list)))    

差距还是挺大的，这里面最优雅的方式就是用lambda函数，用mapcar对队列中每个元素单独处理。优美之极。

1. 经过好几年的审议，政府委员会决定列表应该由cdr指向第一个元素，而car指向剩下的列表。定义符合政府版本的以下函数：

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

(a)
(defun cons (x y)
    (let ((ls '(nil . nil)))
        (setf   (cdr ls) x
                (car ls) y)
        ls))
(b)  要解决 3.6 (b)，你需要使用到 6.3 节的参数 &rest
(c) 
(defun length (ls)
    (if ls
        (+ 1 (length (car ls)))
        0))  递归方法用的真多
(d)
(defun member (obj ls)
    (if (consp ls)
        nil
        (if (eql (cdr ls) obj)
            ls
            (member obj (car ls))))) 

1. 定义一个函数，接受一个列表并用点状表示法打印出来：

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

我写的，不能处理嵌套的情况    还是过程式思维
(defun showdots (x)   
    (let ((len (length x)))
        (mapcar #'(lambda (x) (format t "(~A . " x)) x)
        (format t "NIL ")
        (do ((i 1 (+ i 1)))
            ((> i len) 'nil)
        (format t ")"))))  
(defun showdots (ls)
    (format t "~A" (showdots-rec ls)))
(defun showdots-rec (ls)
    (if ls
        (if (atom ls)
            ls
            (format nil "(~A . ~A)" (showdots-rec (car ls)) (showdots-rec (cdr ls))))))
递归的使用，函数式编程思维。代码简单。

9. 写一个程序来找到3.15节里表示的网络，最长有限的路径（不重复）。网络可能包含循环。

(defun longest-path (start end net)
    (bfs-l end (list (list start)) net nil))
(defun bfs-l (end queue net sol)
    (if queue
        (let ((path (car queue)))
            (let ((node (car path)))
                (bfs-l  end 
                        (append (cdr queue) (new-paths path node net)) 
                        net
                        (if (eql node end) path sol))))
        (reverse sol)))
(defun new-paths (path node net)
    (let ((acc nil))
        (dolist (x (cdr (assoc node net)))
            (or (member x path)
                (push (cons x path) acc)))
        acc))
(longest-path 'a 'd *net*)
  0: (LONGEST-PATH A D ((A B C) (B A C) (C A B D) (D C)))
    1: (BFS-L D ((A)) ((A B C) (B A C) (C A B D) (D C)) NIL)
      2: (NEW-PATHS (A) A ((A B C) (B A C) (C A B D) (D C)))
      2: NEW-PATHS returned ((C A) (B A))
      2: (BFS-L D ((C A) (B A)) ((A B C) (B A C) (C A B D) (D C)) NIL)
        3: (NEW-PATHS (C A) C ((A B C) (B A C) (C A B D) (D C)))
        3: NEW-PATHS returned ((D C A) (B C A))
        3: (BFS-L D ((B A) (D C A) (B C A)) ((A B C) (B A C) (C A B D) (D C))
                  NIL)
          4: (NEW-PATHS (B A) B ((A B C) (B A C) (C A B D) (D C)))
          4: NEW-PATHS returned ((C B A))
          4: (BFS-L D ((D C A) (B C A) (C B A))
                    ((A B C) (B A C) (C A B D) (D C)) NIL)
            5: (NEW-PATHS (D C A) D ((A B C) (B A C) (C A B D) (D C)))
            5: NEW-PATHS returned NIL
            5: (BFS-L D ((B C A) (C B A)) ((A B C) (B A C) (C A B D) (D C))
                      (D C A))
              6: (NEW-PATHS (B C A) B ((A B C) (B A C) (C A B D) (D C)))
              6: NEW-PATHS returned NIL
              6: (BFS-L D ((C B A)) ((A B C) (B A C) (C A B D) (D C)) (D C A))
                7: (NEW-PATHS (C B A) C ((A B C) (B A C) (C A B D) (D C)))
                7: NEW-PATHS returned ((D C B A))
                7: (BFS-L D ((D C B A)) ((A B C) (B A C) (C A B D) (D C))
                          (D C A))
                  8: (NEW-PATHS (D C B A) D ((A B C) (B A C) (C A B D) (D C)))
                  8: NEW-PATHS returned NIL
                  8: (BFS-L D NIL ((A B C) (B A C) (C A B D) (D C)) (D C B A))
                  8: BFS-L returned (A B C D)
                7: BFS-L returned (A B C D)
              6: BFS-L returned (A B C D)
            5: BFS-L returned (A B C D)
          4: BFS-L returned (A B C D)
        3: BFS-L returned (A B C D)
      2: BFS-L returned (A B C D)
    1: BFS-L returned (A B C D)
  0: LONGEST-PATH returned (A B C D)
(A B C D)

(or (member x path) 这句比较关键，new-paths只取那些路径长的，因此如果节点ｘ已经是path的成员了，表示有循环产生，此时就不记录这条路径。
bfs-l的基本思路：对于维护了未搜索路径的序列queue，取其第一个未搜索路径及其第一个节点（节点是倒序放置的），由该未搜索路径及第一个节点，利用new-paths来找到该节点的下方节点，并生成新的未搜索路径并加入到queue的后端。BFS算法对于每层都搜索完毕才会进入下一层，因此叫做广度优先搜索。