Elisp 基本数据类型：cons cell

Table of Contents

CONS CELL 和列表

cons cell

cons cell 在概念上就是两个有顺序的元素，第一个叫 CAR，第二个叫 CDR，cons cell 也就是 construction of cells。car 函数用于取得 cons cell 的 CAR 部分，cdr 函数用于取得 cons cell 的 CDR 部分。

cons cell 如此简单，但是它却能衍生出许多高级的数据结构，比如链表、树、关联表等。

'(1 . 2)                                ; => (1 . 2)
'(?a . 1)                               ; => (97 . 1)
'(1 . "a")                              ; => (1 . "a")
'(1 . nil)                              ; => (1)
'(nil . nil)                            ; => (nil)

表达式前面的 ’ 号，是一个特殊的函数 quote，它的作用是将它的参数返回而不求值。否则 eval-last-sexp 会对读入的 S-表达式求值，如果读入的 S-表达式是一个 cons cell 的话，求值时会把这个 cons cell 的第一个元素作为一个函数来调用。事实上，这些例子的第一个元素都不是一个函数，这样会产生一个错误 invalid-function。

列表

列表包括了 cons cell，但是列表中有一个特殊的元素：空表 nil。

nil
'()

空表不是一个 cons cell，因为它没有 CAR 和 CDR 部分，空表中没有任何内容。但是为了编程的方便，可以认为 nil 的 CAR 和 CDR 都是 nil。

(car nil)                               ; => nil
(cdr nil)                               ; => nil

⚠️️如何将列表看成 cons cell？首先看几个例子：

(cdr '(1 2 3))
;;=> (2 3)

(cdr '(1 2 3 . nil))
;;=> (2 3)

(cdr '(1 2 3 nil))
;;=> (2 3 nil)

'(1 2 . 3) = '(1 . (2 . 3))

'(1 2 3) = '(1 2 3 . nil) = '(1 . (2 . (3 . nil)))

'(1 2 3 nil) = '(1 2 3 nil . nil) = '(1 . (2 . (3 . (nil . nil))))

列表的分类：

按列表 最后一个 cons cell 的 CDR 部分的类型分，可以把列表分为三类：

  1. 如果它是 nil 的话，这个列表被称为「真列表」（true list）；

    '(1 2 3 . nil) = '(1 2 3) = '(1 . (2 . (3 . nil)))

  2. 如果既不是 nil 也不是 cons cell，则这个列表称为「点列表」（dotted list）；

    '(1 2 . 3) = '(1 . (2 . 3))

  3. 如果它指向了列表中之前的一个 cons cell，则称为「环形列表」（circular list）；

    '(1 . #1=(2 3 . #1#))                     ; => (1 2 3 . #1)

测试函数

测试一个对象是否是 cons cell 用 consp，是否是列表用 listp。

(consp '(1 . 2))                        ; => t
(consp '(1 . (2 . nil)))                ; => t
(consp nil)                             ; => nil
(listp '(1 . 2))                        ; => t
(listp '(1 . (2 . nil)))                ; => t
(listp nil)                             ; => t

没有内建的方法测试一个列表是不是一个真列表。通常如果一个函数需要一个真列表作为参数，都是在运行时发出错误，而不是进行参数检查，因为检查一个列表是真列表的代价比较高。

测试一个对象是否是 nil 用 null 函数。只有当对象是空表时，null 才返回空值。

构造函数

使用 cons 函数生成一个 cons cell：

(cons 1 2)                              ; => (1 . 2)
(cons 1 '())                            ; => (1)

也是在列表前面增加元素的方法：

(setq foo '(a b))                       ; => (a b)
(cons 'x foo)                           ; => (x a b)

不过这个例子的 foo 值并没有改变。如果要在加入元素的同事改变列表的值，可以使用 push 宏：

(push 'x foo)                           ; => (x a b)
foo                                     ; => (x a b)

生成一个列表的函数是 list：

(list 1 2 3)                            ; => (1 2 3)

这里的 list 函数和之前的 quote 函数有什么区别呢？quote 是把参数直接返回不进行求值，而 list 和 cons 是对参数求值后再生成一个列表或者 cons cell：

'((+ 1 2) 3)                            ; => ((+ 1 2) 3)
(list (+ 1 2) 3)                        ; => (3 3)

前面提到在列表前端增加元素的方法是用 cons，在列表后端增加元素的函数是用 append：

(append '(a b) '(c))                    ; => (a b c)

append 的功能可以认为它是把第一个参数最后一个列表的 nil 换成第二个参数，比如前面这个例子，第一个参数写成 cons cell 表示方式是(a . (b . nil))，把这个 nil 替换成 (c) 就成了 (a . (b . (c)))。对于多个参数的情况也是一样的，依次把下一个参数替换新列表最后一个 nil 就是最后的结果了。

(append '(a b) '(c) '(d))               ; => (a b c d)

一般来说 append 的参数都要是列表，但是最后一个参数可以不是一个列表，这也不违背前面说的，因为 cons cell 的 CDR 部分本来就可以是任何对象：

(append '(a b) 'c)                      ; => (a b . c)
(append '(a b) '(c))                    ;; 这种就可以继续 append

这样得到的结果就不再是一个真列表了，如果再进行 append 操作就会产生一个错误。

写过 c 的链表类型就知道如果链表只保留一个指针，那么链表只能在一端增加元素。elisp 的列表类型也是类似的， 用 cons 在列表前增加元素比用 append 要快得多 。

append 的参数不限于列表，还可以是字符串或者向量。前面字符串里已经提到可以把一个字符串转换成一个字符列表，同样可能把向量转换成一个列表：

(append [a b] "cd" nil)                 ; => (a b 99 100)

注意前面最后一个参数 nil 是必要的，不然你可以想象得到的结果是什么。

把列表当数组用

elisp 有数组这个数据类型

要得到列表或者 cons cell 里元素，唯一的方法是用 car 和 cdr 函数。很容易明白，car 就是取得 cons cell 的 CAR 部分，cdr 函数就是取得 cons cell 的 CDR 部分。通过这两个函数，我们就能访问 cons cell 和列表中的任何元素。

通过使用 elisp 提供的函数，我们事实上是可以把列表当数组来用。依惯例，我们用 car 来访问列表的第一个元素，cadr 来访问第二个元素，再往后就没有这样的函数了，可以用 nth 函数来访问：

(nth 3 '(0 1 2 3 4 5))                  ; => 3

获得列表一个区间的函数有 nthcdr、last 和 butlast。nthcdr 和 last 比较类似，它们都是返回列表后端的列表。nthcdr 函数返回第 n 个元素后的列表：

(nthcdr 2 '(0 1 2 3 4 5))               ; => (2 3 4 5)

last 函数返回倒数 n 个长度的列表：

(last '(0 1 2 3 4 5) 2)                 ; => (4 5)

butlast 和前两个函数不同，返回的除了倒数 n 个元素的列表。

(butlast '(0 1 2 3 4 5) 2)              ; => (0 1 2 3)

使用前面这几个函数访问列表是没有问题了。但是链表这种数据结构是不适合随机访问的，代价比较高，如果代码中频繁使用这样的函数或者对一个很长的列表使用这样的函数，就应该考虑是不是应该用数组来实现。

直到现在为止， 我们用到的函数都不会修改一个已有的变量，这是函数式编程的一个特点 。只用这些函数编写的代码是很容易调试的，因为你不用去考虑一个变量在执行一个代码后就改变了，不用考虑变量的引用情况等等。

首先学习怎样修改一个 cons cell 的内容。setcar 和 setcdr 可以修改一个 cons cell 的 CAR 部分和 CDR 部分。比如：

(setq foo '(a b c))                     ; => (a b c)
(setcar foo 'x)                         ; => x
foo                                     ; => (x b c)
(setcdr foo '(y z))                     ; => (y z)
foo                                     ; => (x y z)

(setcar foo 'a)                         ; => a
(setcar (cdr foo) 'b)                   ; => b
(setcar (nthcdr 2 foo) 'c)              ; => c
foo

把列表当堆栈用

前面已经提到过可以用 push 向列表头端增加元素，在结合 pop 函数，列表就可以做为一个堆栈了。

(setq foo nil)                          ; => nil
(push 'a foo)                           ; => (a)
(push 'b foo)                           ; => (b a)
(pop foo)                               ; => b
foo                                     ; => (a)

重排列表

如果一直用 push 往列表里添加元素有一个问题是这样得到的列表和加入的顺序是相反的。通常我们需要得到一个反向的列表。reverse 函数可以做到这一点：

(setq foo '(a b c))                     ; => (a b c)
(reverse foo)                           ; => (c b a)

需要注意的是使用 reverse 后 foo 值并没有改变，函数 nreverse 也可以返回逆序的列表，与前面的 reverse 差别就在于它是一个有破坏性的函数，nreverse 会修改 foo 的值。

(nreverse foo)                          ; => (c b a)
foo                                     ; => (a)

现在 foo 指向的是列表的末端，使用 nreverse 的唯一的好处是速度快，省资源。所以如果你只是想得到逆序后的列表就放心用 nreverse，否则还是用 reverse 的好。

elisp 还有一些是具有破坏性的函数。最常用的就是 sort 函数：

(setq foo '(3 2 4 1 5))                 ; => (3 2 4 1 5)
(sort foo '<)                           ; => (1 2 3 4 5)
foo                                     ; => (3 4 5)

如果既要保留原列表，又要进行 sort 操作怎么办呢？可以用 copy-sequence 函数。这个函数只对列表进行复制，返回的列表的元素还是原列表里的元素，不会拷贝列表的元素。

nconc 和 append 功能相似，但是它会修改除最后一个参数以外的所有的参数，nbutlast 和 butlast 功能相似，也会修改参数。这些函数都是在效率优先时才使用。总而言之，以 n 开头的函数都要慎用。

把列表当集合用

列表可以作为无序的集合。合并集合用 append 函数。去除重复的 equal 元素用 delete-dups。查找一个元素是否在列表中，如果测试函数是用 eq，就用 memq，如果测试用 equal，可以用 member。删除列表中的指定的元素，测试函数为 eq 对应 delq 函数，equal 对应 delete。还有两个函数 remq 和 remove 也是删除指定元素。它们的差别是 delq 和 delete 可能会修改参数，而 remq 和 remove 总是返回删除后列表的拷贝。注意前面这是说的是可能会修改参数的值，也就是说可能不会，所以保险起见，用 delq 和 delete 函数要么只用返回值，要么用 setq 设置参数的值为返回值。

(setq foo '(a b c))                     ; => (a b c)
(remq 'b foo)                           ; => (a c)
foo                                     ; => (a b c)
(delq 'b foo)                           ; => (a c)
foo                                     ; => (a c)
(delq 'a foo)                           ; => (c)
foo                                     ; => (a c)

把列表当关联表（map）

用在 elisp 编程中，列表最常用的形式应该是作为一个关联表了。所谓关联表，就是可以用一个字符串（通常叫关键字，key）来查找对应值的数据结构。由列表实现的关联表有一个专门的名字叫 association list。尽管 elisp里也有 hash table，但是 hash table 相比于 association list 至少这样几个缺点：

  • hash table 里的关键字（key）是无序的，而 association list 的关键字 可以按想要的顺序排列
  • hash table 没有列表那样丰富的函数，只有一个 maphash 函数可以遍历列 表。而 association list 就是一个列表，所有列表函数都能适用
  • hash table 没有读入语法和输入形式，这对于调试和使用都带来很多不便

所以 elisp的hash table 不是一个首要的数据结构，只要不对效率要求很高，通常直接用association list。数组可以作为关联表，但是数组不适合作为与人交互使用数据结构（毕竟一个有意义的名字比纯数字的下标更适合人脑）。所以关联表的地位在 elisp 中就非比寻常了，emacs 为关联表专门用 c 程序实现了查找的相关函数以提高程序的效率。在 association list 中关键字是放在元素的 CAR 部分，与它对应的数据放在这个元素的 CDR 部分。根据比较方法的不同，有 assq 和assoc 两个函数，它们分别对应查找使用 eq 和 equal 两种方法。例如：

(assoc "a" '(("a" 97) ("b" 98)))        ; => ("a" 97)
(assq 'a '((a . 97) (b . 98)))          ; => (a . 97)

通常我们只需要查找对应的数据，所以一般来说都要用 cdr 来得到对应的数据：

(cdr (assoc "a" '(("a" 97) ("b" 98))))  ; => (97)
(cdr (assq 'a '((a . 97) (b . 98))))    ; => 97

assoc-default 可以一步完成这样的操作：

(assoc-default "a" '(("a" 97) ("b" 98)))          ; => (97)

如果查找用的键值（key）对应的数据也可以作为一个键值的话，还可以用 rassoc 和 rassq 来根据数据查找键值：

(rassoc '(97) '(("a" 97) ("b" 98)))     ; => ("a" 97)
(rassq '97 '((a . 97) (b . 98)))        ; => (a . 97)

如果要修改关键字对应的值，最省事的作法就是用 cons 把新的键值对加到列表的头端。但是这会让列表越来越长，浪费空间。如果要替换已经存在的值，一个想法就是用 setcdr 来更改键值对应的数据。但是在更改之前要先确定这个键值在对应的列表里，否则会产生一个错误。另一个想法是用 assoc 查找到对应的元素，再用 delq 删除这个数据，然后用 cons 加到列表里：

(setq foo '(("a" . 97) ("b" . 98)))     ; => (("a" . 97) ("b" . 98))

;; update value by setcdr
(if (setq bar (assoc "a" foo))
    (setcdr bar "this is a")
  (setq foo (cons '("a" . "this is a") foo))) ; => "this is a"
foo                         ; => (("a" . "this is a") ("b" . 98))
;; update value by delq and cons
(setq foo (cons '("a" . 97)
                (delq (assoc "a" foo) foo))) ; => (("a" . 97) ("b" . 98))

如果不对顺序有要求的话，推荐用后一种方法吧。这样代码简洁，而且让最近更新的元素放到列表前端，查找更快。

把列表当树用

TODO

遍历列表

其中 var 是一个临时变量，在 body 里可以用来得到列表中元素的值。使用 dolist 的好处是不用写lambda 函数。一般情况下它的返回值是 nil，但是你也可以指定一个值作为返回值（我觉得这个特性没有什么用，只省了一步而已）：

(dolist (foo '(1 2 3))
  (incf foo))                           ; => nil
(setq bar nil)
(dolist (foo '(1 2 3) bar)
  (push (incf foo) bar))                ; => (4 3 2)

其他常用函数

如果看过一些函数式语言教程的话，一定对 fold（或叫 accumulate、reduce）和 filter 这些函数记忆深刻。不过 elisp 里好像没有提供这样的函数。remove-if 和 remove-if-not 可以作 filter 函数，但是它们是 cl 里的，自己用用没有关系，不能强迫别人也跟着用，所以不能写到 elisp 里。如果不用这两个函数，也不用别人的函数的话，自己实现不妨用这样的方法：

(defun my-remove-if (predicate list)
  (delq nil (mapcar (lambda (n)
                      (and (not (funcall predicate n)) n))
                    list)))
(defun evenp (n)
  (= (% n 2) 0))
(my-remove-if 'evenp '(0 1 2 3 4 5))    ; => (1 3 5)

fold 的操作只能用变量加循环或 mapc 操作来代替了：

(defun my-fold-left (op initial list)
  (dolist (var list initial)
    (setq initial (funcall op initial var))))
(my-fold-left '+ 0 '(1 2 3 4))          ; => 10

这里只是举个例子，事实上直接用函数里的遍历操作更好一些。

产生数列常用的方法是用 number-sequence

解析文本时一个很常用的操作是把字符串按分隔符分解，可以用 split-string 函数：

(split-string "key = val" "\\s-*=\\s-*")  ; => ("key" "val")

与 split-string 对应是把几个字符串用一个分隔符连接起来，这可以用 mapconcat 完成。比如：

(mapconcat 'identity '("a" "b" "c") "\t") ; => "a   b   c"

identity 是一个特殊的函数，它会直接返回参数。mapconcat 第一个参数是一个函数，可以很灵活的使用。