CH3: 列表

LISP

---

《ANSI COMMON LISP》读书笔记

---

构造（cons）

• cons真正做的事情是把两个对象结合成一个有两部分的对象，称之为cons对象。概念上来说，一个cons是一对指针，第一个是car，第二个是cdr。
• 我们往往不会把列表想成是成对的，但它们可以这样被定义。任何非空的列表，都可以被视为一对由列表第一个元素及列表其余元素所组成的列表。LISP列表体现了这个概念。LISP的惯例是使用car代表列表的第一个元素，而用cdr代表列表的其余的元素。
• 列表不是不同的对象，而是像cons这样的方式连接起来。
• 在nil上面建立东西时产生的列表由一个cons所组成，内含一个car和cdr指针。car指针让你取得元素，而cdr让你取得列表内其余的东西。
• 如果参数是一个cons对象，函数consp返回真。所以我们可以定义自己的listp：

(defun listp. (x)
    (or (null x) (consp x)))

• 因为所有不是cons对象的东西，就是一个原子，因此判断式atom可以这样定义：

(defun atom. (x)
    (not (consp x)))

• nil既是一个原子也是一个列表。

等式（equality）

• 用同样的参数调用cons两次，得到的数值看起来一样，但实际上是两个不同的对象：

> (eql (cons 'a nil) (cons 'a nil))
NIL

• CL提供了判断两个列表是否有相同元素的判断式：equal。

CL-USER> (equal (cons 'a nil) (cons 'a nil))
T

为什么LISP没有指针

• 在LISP，你永远不用使用指针，因为语言帮你处理好指针了。举例：

> (setf x '(a b c))
(A B C)
> (setf y x)
(A B C)

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

> (eql x y)
T

建立列表

• 函数copy-list接受一个列表，然后返回此列表的复本。新的列表有同样的元素，但是装在新的cons对象里：

> (setf x '(a b c)
        y (copy-list x))
(A B C)

• 函数append返回任何数目的列表串接：

> (append '(a b) '(c d) 'e)
（A B C D . E)

奇怪的点？

压缩

游程编码（run-length encoding)

(defun compress (x)
    (if (consp x)
        (compr (car x) 1 (cdr x))
        x))
(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 n-elts (elt n)
    (if (> n 1)
        (list n elt)
        elt))

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

• elt：上一个我们看过的元素
• n：连续出现的次数
• lst：还没有检查过的列表部分

解压函数

(defun uncompress (lst)
    (if (null lst)
        nil
        (let    ((elt (car lst))
                (rest (uncompress (cdr lst))))
            (if (consp elt)
                (append (apply #'list-of elt)
                    rest)
                (cons elt rest)))))
(defun list-of (n elt)
    (if (zerop n)
        nil
        (cons elt (list-of (- n 1) elt))))

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

访问（Acess）

• 要找到列表特定位置的元素，可以调用nth。

> (nth 0 '(a b c))
A

• 要想找第n个cdr，就调用nthcdr。

> (nthcdr 2 '(a b c))
C

nth与nthcdr都是零索引的。两个函数几乎做一件事情，nth等同于nthcdr的car。

(defun nthcdr. (n lst)
    (if (zero n)
        lst
        (nthcdr. (- n 1) (cdr lst))))

• 函数last返回列表的最后一个cons对象：

> (last '(a b c))
(C)

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

• CL定义了函数first到tenth可以取得列表对应的元素。这些函数不是如它们名字一样零索引的。(second x)等同于nth 1 x)。
• CL还定义了像caddr这样形式cxr的函数。

映射函数（Mapping Functions）

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

> (mapcar #'(lambda (x) (+ x 10))
        '(1 2 3))
(11 12 13)
> (mapcar #'list
        '(a b c)
        '(1 2 3 4))
((A 1) (B 2) (C 3))
> (mapcar #'list
        '(1 2 3 4))
        '(a b c)
((1 A) (2 B) (3 C))
> (mapcar #'list
        '(1 2 3 4))
        '(a b c d)
((1 A) (2 B) (3 C) (4 D))

• maplist接受同样的参数，将列表的渐进的下一个cdr传入函数。

> (maplist #' (lambda (x) x)
            '(a b c))
((A B C) (B C) (C))

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

树

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

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

(defun copy-tree. (tr)
    (if (atom tr)
        tr
        (cons   (copy-tree. (car tr))
                (copy-tree. (cdr tr)))))

• subst用于替换树中的元素。substitute替换序列中的元素。

> (subst 'y 'x '(and (integerp x) (zerop (mod x 2))))
(AND (INTEGERP Y) (ZEROP (MOD Y 2)))

我们定义自己版本的subst。

(defun subst. (new old tree)
    (if (eql tree old)
        new
        (if (atom tree)
            tree
            (cons   (subst. new old (car tree))
                    (subst. new old (cdr tree))))))

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

理解递归

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

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

集合

• member返回由寻找对象所开始的那部分。

> (member 'b '(a b c))
(B C)

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

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

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

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

这个例子里，我们询问是否有一个元素的car是a。

• 如果我们像要找到一个元素满足任意的判断式，如oddp，奇数则返回真——我们可以使用member-if：

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

我们自己写法：

(defun member-if. (fn lst)
    (and (consp lst)
        (if (funcall fn (car lst))
            lst
            (member-if. fn (cdr lst)))))

• 函数adjoin像条件式的cons。它接受一个对象和一个列表，如果对象还不是列表的成员，才构造对象至列表上。

> (adjoin 'b '(a b c))
(A B C)
> (adjoin 'z '(a b c))
(Z A B C)

• 集合论中的并集、交集以及补集由函数union、intersection以及set-difference实现的。

序列（Sequences）

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

• 函数length返回序列中元素的数目。

> (length '(a b c))
3

• 要复制序列的一部分，我们使用subseq。第二个参数（必须的）是第一个引用进来的元素位置，第三个参数（可选的）是第一个不引用进来的元素位置。

> (subseq '(a b c d) 1 2)
(B)
> (subseq '(a b c d) 1)
(B C D)

• 函数reverse返回于其参数相同元素的一个序列，但顺序颠倒。

> (reverse '((a b) c d (e f)))
((E F) D C (A B))

• 使用上面三个函数可以定义检测是否回文的函数：

(defun mirror. (s)
    (let ((len (length s)))
        (and    (evenp len)
                (let ((mid (/ len 2)))
                    (equal (subseq s 0 mid)
                        (reverse (subseq s mid)))))))
> (mirror. '(a b a))
NIL
> (mirror. '(a b b a))
T
> (mirror. '(a b c b a))
NIL                         

• CL中有一个内置排序函数sort。接受一个序列和一个比较参数的函数，返回函数处理后的有同样元素的序列。

`` CommonLisp

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

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

• every some

栈（stacks）

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

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

(let ((x (car lst)))
    (setf lst (cdr lst))
    x)
<div class="md-section-divider"></div>

• 可以用push来定义给列表使用的互动版reverse。

(defun reverse. (lst)
    (let ((acc nil))
        (dolist (elt lst)
            (push elt acc))
        acc))
<div class="md-section-divider"></div>

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

• pushnew宏是push的变种，使用了adjoin而不是cons:

CL-USER> (let ((x '(a b)))
       (pushnew 'c x)
       (pushnew 'a x)
       x)
(C A B)
<div class="md-section-divider"></div>

点状列表（Dotted Lists）

调用list所构造的列表，这种列表精确地说称之为正规列表（properlist）。一个正规列表可以是NIL或cdr是正规列表的cons对象。
我们可以定义一个只对正规列表返回真的判断式：

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

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

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

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

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

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

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

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

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

CL-USER> (setf x '(a . b))
(A . B)
CL-USER> (car x)
A
CL-USER> (cdr x)
B
CL-USER> (setf x '(a b)
(A B)
CL-USER> (car x)
A
CL-USER> (cdr x)
(B)
<div class="md-section-divider"></div>

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

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

(a . (b . nil))
(a . (b))
(a b . nil)
(a b)
<div class="md-section-divider"></div>

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

关联列表（Assoc-Lists）

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

CL-USER> (setf trans '((+ . "add") (- . "substract")))
((+ . "add") (- . "substract"))
CL-USER> (assoc '+ trans)
(+ . "add")
CL-USER> (assoc '* trans)
NIL
CL-USER> 
<div class="md-section-divider"></div>

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

定义自己的assoc:

(defun assoc. (key alist)
    (and (consp alist)
        (let ((pair (car alist)))
            (if (eql key (car pair))
                pair
                (assoc. key (cdr alist))))))
<div class="md-section-divider"></div>

---

示例：最短路径（Example: Shortest Path）

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

    / ->b
  /     |
a       |      
 \      ~ 
   \ --->c---->d
<div class="md-section-divider"></div>

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

(defun shortest-path (start end net)
    (bfs end (list (list start)) net))
(defun bfs (end queue net)
    (if (null queue)
        nil 
        (let ((path (car queue)))
            (let ((node (car path)))
                (if (eql node end)
                    (reverse path)
                    (bfs end
                        (append (cdr queue)
                                (new-paths path node net))
                        net))))))
(defun new-paths (path node net)
    (mapcar #' (lambda (n)
                    (cons n path))
            (cdr (assoc node net))))
<div class="md-section-divider"></div>

这是广度有限搜索算法（breadth-first search）

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

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

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

((A))
((B A) (C A))
((C A) (C B A))
((C B A) (D C A))
((D C A) (D C B A))

垃圾（grabages）

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

总结