CH3: 列表

布满荆棘的人生 2022-08-07 09:46 172阅读 0赞

#### 作业部落与简书同步发布 ####

--------------------

*《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="se-preview-section-delimiter"></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="se-preview-section-delimiter"></div>

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

(defun reverse. (lst)
        (let ((acc nil))
            (dolist (elt lst)
                (push elt acc))
            acc))
    
    
    
    
    <div class="se-preview-section-delimiter"></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="se-preview-section-delimiter"></div>

## 点状列表（Dotted Lists） ##

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

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

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

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

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

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

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

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

> (cons 'a (cons 'b (cons 'c 'd)))
    (A B C . D)
    
    
    
    
    <div class="se-preview-section-delimiter"></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="se-preview-section-delimiter"></div>

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

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

(a . (b . nil))
    (a . (b))
    (a b . nil)
    (a b)
    
    
    
    
    <div class="se-preview-section-delimiter"></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="se-preview-section-delimiter"></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="se-preview-section-delimiter"></div>

--------------------

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

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

/ ->b
      /     |
    a       |      
     \      ~ 
       \ --->c---->d
    
    
    
    
    <div class="se-preview-section-delimiter"></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="se-preview-section-delimiter"></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="se-preview-section-delimiter"></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`的程序。典型的方法是写出一个**纯函数风格**，使用很多列表的第一版程序。当 程序金华时，你可以在代码的关键部分使用破坏性函数或别种数据结构。

## 总结 ##