ANSI Common Lisp 学习笔记 第三章

* 第三章：列表
** #'eql and #'equal 每一次你调用 cons 时， Lisp 会配置一块新的内存给两个指针。所以如果我们用同样的参数调用 cons 两次，我们得到两个数值看起来一样，但实际上是两个不同的对象：

(eql (cons 'a nil) (cons 'a nil))

NIL

如果我们也可以询问两个列表是否有相同元素，那就很方便了。 Common Lisp 提供了这种目的另一个判断式： equal 。而另一方面 eql 只有在它的参数是相同对象时才返回真，

(setf x (cons 'a nil))

(A)

(eql x x)

T
本质上 equal 若它的参数打印出的值相同时，返回真：

(equal x (cons 'a nil))

T
** #'copy-list 函数 copy-list 接受一个列表，然后返回此列表的复本。新的列表会有同样的元素，但是装在新的 Cons 对象里 这个定义暗示着 x 与 (copy-list x) 会永远 equal ，并永远不 eql ，除非 x 是 NIL 。
** #'append

(setf x '(a b) y '(c d) z 'e)

(setf app (append x y z))

(setf (car x) 'aa)

app

(setf z 'ee)

app ;; 这里Clozure和Paul Graham的实现不太一样。
** #'nth zero-indexed
** #'nthcdr zero-indexed
** #'zerop
** #'last 函数 last 返回列表的最后一个 Cons 对象
** #'first second ... Common Lisp 定义了函数 first 直到 tenth 可以取得列表对应的元素。这些函数不是零索引的
** #'cadr ... Common Lisp 定义了像是 caddr 这样的函数，它是 cdr 的 cdr 的 car 的缩写 ( car of cdr of cdr )。所有这样形式的函数 cxr ，其中 x 是一个字串，最多四个 a 或 d
** #'mapcar Common Lisp 提供了数个函数来对一个列表的元素做函数调用。最常使用的是 mapcar ，接受一个函数以及一个或多个列表，并返回把函数应用至每个列表的元素的结果，直到有的列表没有元素为止 #+ example:

(mapcar #'list '(a b c d)
               '(1 2 3)
               '(α β γ))

** #'copy-tree and #'copy-list

(setf a '(1 2 3))

(setf b '(4 5 6))

(setf c 'c)

(setf l1 (list a b c))

(setf l2 (copy-list l1))

(setf l3 (copy-tree l1))

(setf (car a) 0)

(setf (car b) 0)

(setf c 'd)

l1 l2 l3

(setf (caddr l1) 'D)

l1 l2 l3

((0 2 3) (4 5 6) C)

((0 2 3) (4 5 6) C)

((1 2 3) (4 5 6) C)

;deep copy

((0 2 3) (0 5 6) D)

((0 2 3) (0 5 6) C)

((1 2 3) (4 5 6) C)

** #'integerp
** #'member and #'member-if

(member '(a) '((a) (z)) :test #'equal)

(member 'a '((a b) (c d)) :key #'car)

(member-if #'oddp '(2 3 4))

** #'adjoin #'union #'intersection #'set-difference 函数 adjoin 像是条件式的 cons 。它接受一个对象及一个列表，如果对象还不是列表的成员，才构建对象至列表上。

(adjoin 'b '(a b c))

(adjoin 'z '(a b c))

(union '(a b c q) '(c b t s))

(intersection '(a b c) '(b b c))

(set-difference '(a b c d e) '(b e))

** #'length #'subseq #'reverse

(length '(a b c))

(subseq '(a b c d) 1 3)

(reverse '(a b c))

** #'sort : destructive

(sort '(0 2 1 3 8) #'<)

** #'every and #'some 如果它们输入多于一个序列时，判断式必须接受与序列一样多的元素作为参数，而参数从所有序列中一次提取一个

(every #'oddp '(1 3 5))

(some #'evenp '(1 2 3))

(every #''(1 3 5) '(0 2 4))

** #'push #'pop and #'pushnew (macro) 用 Cons 对象来表示的列表，很自然地我们可以拿来实现下推栈 (pushdown stack)。这太常见了，以致于 Common Lisp 提供了两个宏给堆叠使用： (push x y) 把 x 放入列表 y 的前端。而 (pop x) 则是将列表 x 的第一个元素移除，并返回这个元素。 pushnew 宏是 push 的变种，使用了 adjoin 而不是 cons #+example

(let ((x '(a b)))
     (pushnew 'c x)
     (pushnew 'a x)
     x)

** Assoc-lists 用 Cons 对象来表示映射 (mapping)也是很自然的。一个由 Cons 对象组成的列表称之为关联列表(assoc-listor alist)。这样的列表可以表示一个翻译的集合，举例来说：

(setf trans '((+ . "add") (- . "subtract")))

关联列表很慢，但是在初期的程序中很方便。 Common Lisp 有一个内置的函数 assoc ，用来取出在关联列表中，与给定的键值有关联的 Cons 对：

(assoc '+ trans)

(assoc '* trans)

** TODO 3.15 Example: Shortest Path
** Exercise
*** 1 omitted
*** 2 写一个保留原本列表中元素顺序的 union 版本：

(defun new-union (la lb)
  (reverse (union lb (reverse la))))

;; 一次成功，耶

(new-union '(a b c) '(b a d))

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

(defun occurrences (lst)
  (labels ((insert (mem array)
		   (let ((result (member mem array :key #'car)))
		     (cond (result (incf (cdar result)) array)
			   (t (push (cons mem 1) array)))))
	   (occurrences-aid (lst array)
			    (if (null lst)
				(sort array #'(lambda (a b) ((cdr a) (cdr b))))
			      (let ((new-array (insert (car lst) array)))
				(occurrences-aid (cdr lst) new-array)))))
    (occurrences-aid lst nil)))

(occurrences '(a b a d a c d c a))

;; if version, original one.

(defun occurrences (lst)
  (labels ((insert (mem array)
		   (let ((result (member mem array :key #'car)))
		     (if result
			 (progn
			   (incf (cdar result))
			   array)
		       (push (cons mem 1) array))))
	   (occurrences-aid (lst array)
			    (if (null lst)
				(sort array #'(lambda (a b) ((cdr a) (cdr b))))
			      (let ((new-array (insert (car lst) array)))
				(occurrences-aid (cdr lst) new-array)))))
    (occurrences-aid lst nil)))

(occurrences '(a b a d a c d c a))

*** 4 为什么 (member '(a) '((a) (b))) 返回 nil？
*** 5 假设函数 pos+ 接受一个列表并返回把每个元素加上自己的位置的列表：

(pos+ '(7 5 1 4))

(7 6 3 7)

使用 (a) 递归 (b) 迭代 (c) mapcar 来定义这个函数。 ;(a)

(defun pos+ (lst)
  (if (null lst)
      nil
    (cons (car lst)
	  (pos+ (mapcar #'(lambda (x) (incf x)) (cdr lst))))))

;(b)

(defun pos+ (lst &optional (pos 0))
  (if (null (nth pos lst))
      lst
    (progn (incf (nth pos lst) pos)
	   (pos+ lst (+ 1 pos)))))

;(c)

(defun pos+ (lst)
  (let ((pos -1))
    (mapcar #'(lambda (n) (incf pos) (incf n pos)) lst)))

*** 6 略
*** 7 略
*** 8 定义一个函数，接受一个列表并用点状表示法印出

(defun showdots (lst &optional (output-target t))
  "if t then print else return the string"
  (if (null lst)
      "NIL"
    (format output-target
	    "(~A . ~A)"
	    (car lst)
	    (showdots (cdr lst) nil))))

;(showdots '(a b c) t) ;(showdots '(a b c) nil)

(showdots '(a b c))

*** 9 略