理解Emacs Lisp的 List

官方文档对于 List 的描述如下：

A list is a series of cons cells, linked together so that the CDR slot of each cons cell holds either the next cons cell or the empty list. The empty list is actually the symbol nil.

List 是由一系列的 Cons Cell 组成的，要理解 List，必须要先理解 Cons Cell。Cons Cell 看起来很简单，它包含两个元素，第一个叫做 car ，第二个叫做 cdr 。跟 C++的 std::pair 非常相似，car 就是 first，cdr 就是 second。下图的 Cons Cell，car 是字符串 a，cdr 是整数 1。

可以通过 cons 函数来构造 Cons Cell: (cons "a" 1) ，也可以通过点分法来写: '("a" . 1) 。

car 和 cdr 可以是其他任何的类型。如果 cdr 也是一个 Cons Cell，就会是如下的结构。

继续递归下去，就会得到一个深层嵌套的结构。

如果换一种表达方式，看起来就像是我们最熟悉的链表了。

上面的结构用 cons 函数表达是这样的: (cons 1 (cons 2 (cons 3 nil))) 。要注意最后 Cons Cell 的 cdr 是 nil。可以看到这个结构用 cons 写起来比较麻烦，所以 elisp 提供了 list 函数来构造 List，这样写起来就比较简单了: (list 1 2 3) 。可以验证，这两个写法是等价的：

(equal (list 1 2 3) (cons 1 (cons 2 (cons 3 nil)))) ;; 结果为t

从文档的描述看的确如此。List 要么是 nil，要么是一系列的 Cons Cell。elisp 提供了 listp 这个谓词函数, 用于检查一个对象是否是 List：

(listp (cons 1 2))
(listp (cons 1 (cons 2 (cons 3 nil))))
(listp nil)

以上结果都是 t，这些都是 List，跟文档一致。

最后的 nil

看到这里，你可能会跟当时的我一样产生疑问：假如这个 list 只有两个 Cons Cell，不要最后的 nil，是不是也可以呢？ 也就是 (cons 1 (cons 2 3)) 。它们看起来好像也差不多，都包含三个元素。

做些简单的验证：

(listp (cons 1 (cons 2 3))) ;; t
(equal (list 1 2 3) (cons 1 (cons 2 3))) ;; nil

以上结果表明, (cons 1 (cons 2 3)) 是 list, 但它不等价于 (list 1 2 3) 。

(cons 1 (cons 2 3)) 和 (list 1 2 3) 都是 list，但它们又不一样，那怎么从概念上理解呢？

如果用过 python 或者其他支持高阶函数的语言，应该了解 map 函数。它会对 list 中的每个元素应用某个函数。elisp 中也有类似的高阶函数 mapcar 。

mapcar applies function to each element of sequence in turn, and returns a list of the results.

下面我们用 mapcar 来分别操作 (cons 1 (cons 2 3)) 和 (list 1 2 3) ，看看会有什么样的效果。

(mapcar (lambda (x) (1+ x)) (list 1 2 3)) ;; (2 3 4)
(mapcar (lambda (x) (1+ x)) (cons 1 (cons 2 3))) ;; Lisp error: (wrong-type-argument listp 3)

结果让人摸不着头脑, (cons 1 (cons 2 3)) 明明就是一个 list，为什么用 mapcar 会出现错误呢？

要回答这个问题，需要先看看 mapcar 是怎么实现的。emacs/src/fns.c

{
	Lisp_Object tail = seq;
	for (ptrdiff_t i = 0; i < leni; i++)
	{
	  if (! CONSP (tail))
	    return i;
	  Lisp_Object dummy = call1 (fn, XCAR (tail));
	  if (vals)
	    vals[i] = dummy;
	  tail = XCDR (tail);
	}
}

mapcar 用一个循环遍历 list，用 car 获取第一个元素，应用函数 fn ，然后再拿到 cdr ，继续循环。所以对于 (cons 1 (cons 2 3)) ，循环到第三次时，就会执行 (car 3) 这个逻辑。因为 3 并不是 cons cell，所以会出现错误。

从概念上来说，List 是分为两种的，proper list 和 improper list。以 nil 结尾的就是 proper list，否则就是 improper list。使用 list 函数得到的是 proper list。

Emacs 提供了一个谓词函数 proper-list-p 用于判断是否是 proper list。

(proper-list-p (cons 1 (cons 2 3))) ;; nil
(proper-list-p (list 1 2 3)) ;; 3

搞明白 Cons Cell 和 List 之后，我们再看 Association List (简称 alist)。alist 的用法类似于其他语言中的 map，可以把它用作 key value 的存储结构。

'(("a" . 1) ("b" . 2) ("c" . 3)) 是一个 alist。结构很简单，就是一个 list，每个元素是个 cons cell。

可以通过 assoc 或者 alist-get 函数来查找 key 对应的 value，要注意 assoc 使用 equal 来比较 key 是否相同，而 alist-get 使用 eq。

(assoc "a" '(("a" . 1) ("b" . 2) ("c" . 3))) ;; ("a" . 1)
(alist-get "a" '(("a" . 1) ("b" . 2) ("c" . 3))) ;; nil
(alist-get 'a '((a . 1) (b . 2) (c . 3))) ;; 1

alist 里面的元素不一定全部都是 cons cell，比如下面这个 alist 的第一个元素是字符串，但仍然可以用 assoc 来查找数据。

(assoc "a" '("x" ("a" . 1) ("b" . 2) ("c" . 3))) ;; ("a" . 1)

Property List，简称 plist，跟 alist 类似，也是 key value 的结构。plist 更简单一些，比如 (list :a 1 :b 2) 就是一个 plist。可以通过 plist-get 函数从 plist 中获取数据。 plist-get 也是通过 eq 来判断 key 是否相等的。

(plist-get (list :a 1 :b 2) :a) ;; 1

但 plist 本身并不是一个严格的定义，更像是一种约定。一个普通的 list 也可以是 list。

(plist-get (list 1 2 3) 1) ;; 2

(list 1 2 3) 里面虽然没有 keyword symbol，但照样可以用 plist-get 函数来获取 value。它甚至只有 3 个元素，这都没有任何的影响。所以很难说一个 list 到底是不是 plist。

plist 本身是一维的 list，要遍历 plist 有些麻烦，不能使用 mapcar 或者 dolist，因为这样只能单独的取到 key 或者 value。因此实现了一个函数 plist-map ，类似于 mapcar，但是可以同时获取到 key 和 value。

(defun plist-map (plist f)
  (let ((new-plist))
    (while plist
      (let* ((k (car-safe plist))
             (v (cadr plist))
             (pair (funcall f k v)))
        (setq new-plist (plist-put new-plist (car pair) (cdr pair))))
      (setq plist (cddr plist)))
    new-plist))

emacs 自身是没有提供 plist 和 alist 的谓词函数的，因为概念并不那么清晰。