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 略