[关闭]
@yiltoncent 2015-03-29T15:13:05.000000Z 字数 7727 阅读 898

CH3: 列表

LISP


《ANSI COMMON LISP》读书笔记


构造(cons)

  1. (defun listp. (x)
  2. (or (null x) (consp x)))
  1. (defun atom. (x)
  2. (not (consp x)))

等式(equality)

  1. > (eql (cons 'a nil) (cons 'a nil))
  2. NIL
  1. CL-USER> (equal (cons 'a nil) (cons 'a nil))
  2. T

为什么LISP没有指针

  1. > (setf x '(a b c))
  2. (A B C)
  3. > (setf y x)
  4. (A B C)

当我们把x赋值给y时,内存中于x有关的位置并没有包含这个列表,而是用一个指针指向它。当我们给y赋值时,LISP复制的是指针,而不是列表。此时:

  1. > (eql x y)
  2. T

建立列表

  1. > (setf x '(a b c)
  2. y (copy-list x))
  3. (A B C)
  1. > (append '(a b) '(c d) 'e)
  2. (A B C D . E)

奇怪的点?

压缩

游程编码(run-length encoding)

  1. (defun compress (x)
  2. (if (consp x)
  3. (compr (car x) 1 (cdr x))
  4. x))
  5. (defun compr (elt n lst)
  6. (if (null lst)
  7. (list (n-elts elt n))
  8. (let ((next (car lst)))
  9. (if (eql next elt)
  10. (compr elt (+ n 1) (cdr lst))
  11. (cons (n-elts elt n)
  12. (compr next 1 (cdr lst)))))))
  13. (defun n-elts (elt n)
  14. (if (> n 1)
  15. (list n elt)
  16. elt))

当相同的元素连续出现好几次,这个连续出现的序列被一个列表代替,列表知名出现的次数和出现的元素。
主要的工作有递归函数compr完成。

解压函数

  1. (defun uncompress (lst)
  2. (if (null lst)
  3. nil
  4. (let ((elt (car lst))
  5. (rest (uncompress (cdr lst))))
  6. (if (consp elt)
  7. (append (apply #'list-of elt)
  8. rest)
  9. (cons elt rest)))))
  10. (defun list-of (n elt)
  11. (if (zerop n)
  12. nil
  13. (cons elt (list-of (- n 1) elt))))

以上两种写法不是一个有经验的LISP程序员用的写法。它的效率很差,它没有尽可能的压缩

访问(Acess)

  1. > (nth 0 '(a b c))
  2. A
  1. > (nthcdr 2 '(a b c))
  2. C

nthnthcdr都是零索引的。两个函数几乎做一件事情,nth等同于nthcdrcar

  1. (defun nthcdr. (n lst)
  2. (if (zero n)
  3. lst
  4. (nthcdr. (- n 1) (cdr lst))))
  1. > (last '(a b c))
  2. (C)

注意,这跟取最后一个元素不一样。要取得列表的最后一个元素,你要取lastcar

映射函数(Mapping Functions)

CL提供数个函数来对一个列表的元素做函数调用
* 最常用的就是mapcar:接受一个函数以及一个或多个列表,并返回把函数应用到每个列表的元素的结果。这有点像apply或者funcall

  1. > (mapcar #'(lambda (x) (+ x 10))
  2. '(1 2 3))
  3. (11 12 13)
  4. > (mapcar #'list
  5. '(a b c)
  6. '(1 2 3 4))
  7. ((A 1) (B 2) (C 3))
  8. > (mapcar #'list
  9. '(1 2 3 4))
  10. '(a b c)
  11. ((1 A) (2 B) (3 C))
  12. > (mapcar #'list
  13. '(1 2 3 4))
  14. '(a b c d)
  15. ((1 A) (2 B) (3 C) (4 D))
  1. > (maplist #' (lambda (x) x)
  2. '(a b c))
  3. ((A B C) (B C) (C))

上述的函数返回输入值,因此直接显示出渐进的下一个cdr对象。
* mapcmapcan

cons对象可以想成是二叉树,car代表左子树,cdr代表右子树。

CL中有几个内置的操作树的函数:
* copy-tree接受一个树,并返回一份副本。

  1. (defun copy-tree. (tr)
  2. (if (atom tr)
  3. tr
  4. (cons (copy-tree. (car tr))
  5. (copy-tree. (cdr tr)))))
  1. > (subst 'y 'x '(and (integerp x) (zerop (mod x 2))))
  2. (AND (INTEGERP Y) (ZEROP (MOD Y 2)))

我们定义自己版本的subst

  1. (defun subst. (new old tree)
  2. (if (eql tree old)
  3. new
  4. (if (atom tree)
  5. tree
  6. (cons (subst. new old (car tree))
  7. (subst. new old (cdr tree))))))

操作树的函数通常有这种形式:carcdr同时做递归。这种函数被称之为双重递归(doubly recursive)。

理解递归

一个程序员在定义一个递归函数时,通常不会特别地去像函数的调用顺序所导致的后果。递归的有点是它精确地让我们更抽象地来设计算法。

递归的方法跟数学中的归纳法很像。

集合

  1. > (member 'b '(a b c))
  2. (B C)

一般情况下,member使用eql来比较对象。你可以使用一种叫做关键字参数的东西来重写缺省的比较方法。多数的CL函数接受一个或多个关键字参数
一个member函数所接受的关键字参数是:test参数。
如果我们想找到一个给定的对象与列表中的成员是否equal,我们可以:

  1. > (member '(a) '((a) (z)) :test #'equal)
  2. ((A) (Z))

另一个member接受的关键字参数是:key参数。借由提供这个参数,你可以在作比较之前,指定一个函数运用在每个元素:

  1. > (member 'a '((a b) (c d)) :key #'car)
  2. ((A B) (C D))

这个例子里,我们询问是否有一个元素的cara

  1. > (member-if #'oddp '(2 3 4))
  2. (3 4)

我们自己写法:

  1. (defun member-if. (fn lst)
  2. (and (consp lst)
  3. (if (funcall fn (car lst))
  4. lst
  5. (member-if. fn (cdr lst)))))
  1. > (adjoin 'b '(a b c))
  2. (A B C)
  3. > (adjoin 'z '(a b c))
  4. (Z A B C)

序列(Sequences)

另一种考虑一个列表的方式是想像成一系列有特定顺序的对象。在CL中,序列包括了列表与向量。

  1. > (length '(a b c))
  2. 3
  1. > (subseq '(a b c d) 1 2)
  2. (B)
  3. > (subseq '(a b c d) 1)
  4. (B C D)
  1. > (reverse '((a b) c d (e f)))
  2. ((E F) D C (A B))
  1. (defun mirror. (s)
  2. (let ((len (length s)))
  3. (and (evenp len)
  4. (let ((mid (/ len 2)))
  5. (equal (subseq s 0 mid)
  6. (reverse (subseq s mid)))))))
  7. > (mirror. '(a b a))
  8. NIL
  9. > (mirror. '(a b b a))
  10. T
  11. > (mirror. '(a b c b a))
  12. NIL

`` CommonLisp

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

  1. `sort`要小心使用,它是具有破坏性的。如果你不想你本来的序列被修改,传入一个副本。
  2. 使用`sort``nth`,可以些一个函数,返回列表中第`n`大的元素:
  3. ``` CommonLisp
  4. (defun nthmost (n lst)
  5. (nth (- n 1)
  6. (sort (copy-list lst) #'>)))
  7. > (nthmost 3 '(9 43 91 93 0 1 4))
  8. 43
  9. <div class="md-section-divider"></div>

栈(stacks)

cons对象来表示的队列,很自然地我们可以拿来实现下推栈(pushdown stack)。
CL提供了两个给堆使用:
* (push x y)x放入队列y的前端,并返回队列。
* (pop x)将列表x的第一个元素移除并返回这个元素。

(push obj lst)等同于(setf lst (cons obj lst))
(pop lst)等同于

  1. (let ((x (car lst)))
  2. (setf lst (cdr lst))
  3. x)
  4. <div class="md-section-divider"></div>
  1. (defun reverse. (lst)
  2. (let ((acc nil))
  3. (dolist (elt lst)
  4. (push elt acc))
  5. acc))
  6. <div class="md-section-divider"></div>

这个版本从空列表开始,然后从lst的第一个元素开始push到空表中。完成时,lst最后一个元素会出现在最前端。

  1. CL-USER> (let ((x '(a b)))
  2. (pushnew 'c x)
  3. (pushnew 'a x)
  4. x)
  5. (C A B)
  6. <div class="md-section-divider"></div>

点状列表(Dotted Lists)

调用list所构造的列表,这种列表精确地说称之为正规列表(properlist)。一个正规列表可以是NILcdr是正规列表cons对象。
我们可以定义一个只对正规列表返回真的判断式:

  1. (defun proper-list. (x)
  2. (or (null x)
  3. (and (consp x)
  4. (proper-list. (cdr x)))))
  5. <div class="md-section-divider"></div>

无论何时你需要一个具有两个字段的列表,你可以使用一个cons对象。

  1. CL-USER> (setf pair (cons 'a 'b))
  2. (A . B)
  3. <div class="md-section-divider"></div>

因为这个cons对象不是一个正规列表,它用点状表示法来显示。在点状表示法中,每个cons对象的carcdr由一个句号隔开来表示。

一个非正规列表的cons对象称之为点状列表。
你也可以用点状表示法表示正规列表,但当LISP显示一个正规列表时,它会使用普通的列表表示法:

  1. > '(a . (b . (c . NIL))) 点状表示法
  2. (A B C) 列表表示法
  3. <div class="md-section-divider"></div>

注意列表由点状表示法于箱子表示法的关联性。
还有一个过渡形式的表示法,介于列表表示及纯点状表示法之间:

  1. > (cons 'a (cons 'b (cons 'c 'd)))
  2. (A B C . D)
  3. <div class="md-section-divider"></div>

(A B)(A . B)的区别

  1. CL-USER> (setf x '(a . b))
  2. (A . B)
  3. CL-USER> (car x)
  4. A
  5. CL-USER> (cdr x)
  6. B
  7. CL-USER> (setf x '(a b)
  8. (A B)
  9. CL-USER> (car x)
  10. A
  11. CL-USER> (cdr x)
  12. (B)
  13. <div class="md-section-divider"></div>

(B)用点状表示法就是:(B . NIL)

(a b)的多种表示方法:

  1. (a . (b . nil))
  2. (a . (b))
  3. (a b . nil)
  4. (a b)
  5. <div class="md-section-divider"></div>

LISP总是使用最后形式来显示列表。

关联列表(Assoc-Lists)

一个由cons对象组成的列表称之为关联列表。这样的列表可以表示一个翻译的集合:

  1. CL-USER> (setf trans '((+ . "add") (- . "substract")))
  2. ((+ . "add") (- . "substract"))
  3. CL-USER> (assoc '+ trans)
  4. (+ . "add")
  5. CL-USER> (assoc '* trans)
  6. NIL
  7. CL-USER>
  8. <div class="md-section-divider"></div>

CL中的内置函数assoc,用于取出在关联列表中,与给定的键值有关联的cons对。

定义自己的assoc:

  1. (defun assoc. (key alist)
  2. (and (consp alist)
  3. (let ((pair (car alist)))
  4. (if (eql key (car pair))
  5. pair
  6. (assoc. key (cdr alist))))))
  7. <div class="md-section-divider"></div>

示例:最短路径(Example: Shortest Path)

函数shortest-path接受一个起始节点目的节点以及一个网络,并返回最短路径。
其中,节点用符号表示,网络则用含以下元素形式的关联列表来表示:
(node . neighbors) 『PS:用关联列表来表示网络节点与临近节点的关系。使用assoc函数就能取得该节点能到达的节点。』

  1. / ->b
  2. / |
  3. a |
  4. \ ~
  5. \ --->c---->d
  6. <div class="md-section-divider"></div>

则上面的最小网络可以这样表示:
(setf min '((a b c) (b c) (c d)))

  1. (defun shortest-path (start end net)
  2. (bfs end (list (list start)) net))
  3. (defun bfs (end queue net)
  4. (if (null queue)
  5. nil
  6. (let ((path (car queue)))
  7. (let ((node (car path)))
  8. (if (eql node end)
  9. (reverse path)
  10. (bfs end
  11. (append (cdr queue)
  12. (new-paths path node net))
  13. net))))))
  14. (defun new-paths (path node net)
  15. (mapcar #' (lambda (n)
  16. (cons n path))
  17. (cdr (assoc node net))))
  18. <div class="md-section-divider"></div>

这是广度有限搜索算法(breadth-first search)

上述程序使用广度优先的方式搜索网络。
要使用广度有限搜索,你需要维护一个含有未探索节点的队列。每一次到达一个节点,检查这个节点是否是你要的。如果不是,则把这个节点的字节点加入队列的尾端,并从队列起始选一个节点,继续搜索。借由总是把较深的节点放在队列的尾端,我们确保网络一次被搜索一层。
我们不仅想要找到节点,还向保有我们怎么到那的记录。所以与其维护一个具有节点的队列(queue),我们维护一个已知路径的队列,每个已知路径都是一列节点。当我们从队列取出一个元素继续搜索时,它是一个含有队列前端节点的列表,而不只是一个节点而已。
函数bfs负责搜索。起初队列只有一个元素,构成表示从起点开始的路径。
所以shortest-path调用bfs,并传入(list (list start))作为初始队列。
bfs函数第一件要考虑的事是,是否还有节点需要探索;如果队列(queue)为空,bfs返回nil指出没有找到路径。如果还有节点需要探索,bfs检查队列前段的节点。如果节点的car部分是我们要找的节点,我们返回这个找到的路径,并且为了可读性的原因我们反转它。如果我们没有找到我们要找到的节点,它有可能在现在节点之后,所以我们把它的子节点加入队列尾端。然后我们递归地调用bfs来继续搜索剩下的队列。

  1. > (shortest-path 'a 'd min)
  2. (A C D)
  3. <div class="md-section-divider"></div>

下面队列是我们连续调用bfs看起来的样子:

  1. ((A))
  2. ((B A) (C A))
  3. ((C A) (C B A))
  4. ((C B A) (D C A))
  5. ((D C A) (D C B A))

垃圾(grabages)

我们不再有任何非让是可以存储的对象叫做垃圾。使用及回首堆所带来的代价有时可以看作cons的代价。除非一个程序从来不丢其任何东西,不然所有的cons对象终究要变成垃圾。consing的问题是,配置空间于清除内存,于程序的常规运行比起来花费昂贵。当写出cons很多的程序是如此简单,我们还是可以写出不使用cons的程序。典型的方法是写出一个纯函数风格,使用很多列表的第一版程序。当 程序金华时,你可以在代码的关键部分使用破坏性函数或别种数据结构。

总结

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注