clisp 学习笔记 2-列表

cons & atom & list

对于列表，应当如此抽象——

可以认为，cons 函数是做这样一件事——把两个对象结合成一个有两个元素的对象，使用 car 取第一个对象，使用 cdr 取其余对象。或者说，car 和 cdr 是两个指针。

这种 cons 表示法叫做箱子表示法（box），因为每一个 cons 对象用箱子表示。而列表，则是一连串箱子。

要注意的是，包含列表的列表叫做嵌套列表，否则叫平坦列表（flatlist），或者叫序列 sequence。

谓词 consp 判断元素是否 cons 对象。不是 cons 对象的就是 atom。列表是特殊的，空列表等同于 nil，它也是 atom，而非空列表是 cons。

因此，我们可以定义 listp——

(defun our-listp (obj)
    (or (null obj) (consp obj))) ; 如果 obj 是 nil，那它是空列表，是列表，如果是 cons 对象，也是列表。

(defun our-atom (obj) ; 为什么不遵守谓词的命名？
    (not (consp obj))) ; 不是 cons 的，就是 atom。因此，其他数据结构，比如序列，也是 atom！

equal & eql

每次调用 cons（和 list），lisp 都会分配一块新的内存给两个指针，因此使用同样的参数调用两次 cons，其数值上一样，但是并非是同一个对象。

(eql (cons 'A nil) (cons 'A nil))
NIL

(equal (cons 'A nil) (cons 'A nil))
T

可见，eql 比较是否是一个对象，equal 比较是否数值相同。就像 python 里 is 和==的关系，前者是判断是否是一个对象——在内存里是同一块地址，后者判断是否数值相同。

指针？不存在的

lisp 只有引用，没有指针。

> (setf x '(1 2 3) y x)
(1 2 3)
> (setf (car x) 3)
3
> x
(3 2 3)
> y
(3 2 3) ; 可见，x 和 y 指向同一个地址
> (eql x y)
T

建立列表

复制列表——copy-list 和 copy-tree

> (defun our-copy-list (lst) ; 只对 flatlist 起作用
    (if (null lst)
        nil
        (cons (car lst) (our-copy-list (cdr lst))))); 可见，只有 cdr 是复制的，这里的 car 如果不是 atom（因而使 cons），那就变成引用了，要出篓子。

; 举个例子
> (setf x '((1 2 3) 1 2) y (copy-list x))
((1 2 3) 1 2)
> (setf (car (car y)) 3) ; 更改的是 y
3
> x
((3 2 3) 1 2) ; 可见，第一个 cons 的 car，即 (1 2 3) 仍旧是被引用了。

> (defun our-copy-tree (lst)
    (if (null lst)
        nil
        (cons (our-copy-tree (car lst)) (our-copy-tree (cdr lst))))) ; 既复制 car，也复制 cdr

其他存取函数

其他存取函数都是通过 car 和 cdr 定义的，nth 和 nthcdr 分别找到第几个位置的 car 和 cdr。nth 相当于是 (car (nthcdr index lst))

它们都是零索引的，即从 0 开始计数。

同时，还有从 fitst 到 tenth，取相对应位置的对象。它们是非零索引的。如，(second x) 相同于 (nth 1 x)

> (nth 0 '(a b c)) ;xxxth 其实是英文的序数词，比如 15th，15 日这样的
A
> (nthcdr 2 '(a b c))
(C)

映射函数（mapping function）

所谓映射函数，就是对列表元素都进行函数调用，将结果作为一个列表返回。最常用的是 mapcar。

此外，maplist 和 mapcar 接受一样的参数，但是 maplist 对每一个 cdr（包括该 cons 本身）进行调用，最终返回结果的 list。

> (mapcar #'(lambda (x) (+ x 10)) '(1 2 3))
(11 12 13)

> (maplist #'(lambda (lst) lst) '(1 2 3)) ;lambda 接受一个 list 而非 atom
((1 2 3) (2 3) (3))

列表模拟的数据结构

这些数据结构都是 cons 对象，它们的操作函数都是共同的，你要抽象成什么结构，就用什么函数。

树（tree）

cons 对象可以想象成二叉树，car 代表左子树，cdr 代表右子树。
比如对 (a (b c) d)，其结构可以想象为——

substitute 接受三个参数，新值，原值，一个序列，它会返回这样一个副本，其中将序列里的所有原值变为新值，要注意的是，这里的原值，新值等，是按 car 找的。

subst 则对树起作用，即它遍历所有 atom 而非原列表的所有 car。

(defun our-subst (new old tree-node)
    (if (equal old tree-node)
        new
        (if (atom tree-node) ; 如果 tree-node 是 atom（包括 nil
            tree-node ; 初始用例被迫使用在这里……
            (cons (our-subst new old (car tree-node))
                  (our-subst new old (cdr tree-node)))))) ; 这种 car 和 cdr 同时进行递归，叫双重递归，遍历树时常用。

集合（set）

集合，同数学或 python 中的 set。

它有 member 函数，测试一个元素是否在集合内，如果是，则返回从这个元素开始的部分。至于为什么这么用，我还不知道。

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

member 同时有 test 和 key 参数，test 参数表明使用什么函数进行测试，key 参数是首先对元素进行处理的函数，简单来说，member 对 set 的每一个元素先用 key 进行转换，然后用 test 对转换后的元素和接受的值进行测试，成功则结束函数，返回此时的 cdr。

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

> (member 3 '((2) (3) (1) (4) (5)) :key #'car :test #'<) ; 测试只有在成功时停止，成功时，3<4，此时返回真，此时的元素为 (4)，取其后的值
; 也可以认为——询问每一个元素的 car 是否满足 3 < 它。

member-if 函数则是测试是否有元素满足一个谓词。

> (member-if #'oddp '(2 4 5 6 7)) ;oddp——奇数谓词
(5 6 7)

adjoin 函数可以认为是 set 的添加，只有在 set 中无此元素，才添加它。它是 cons 的变种

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

然后是并集 (union)、交集 (intersection) 以及补集 (complement)，它们是由函数 union 、 intersection 以及 set-difference 实现的。这个不用多说了。

序列（sequence）

序列可以认为是一系列有特定顺序的对象（虽然是一串 cons 序列，或者说链表模拟的）。

length 函数，返回序列的长度。这个不用解释，都有。

subseq 函数，返回子序列。第一个参数为序列第二个参数是第一个开始引用的元素的 index，第三个参数（可选）是第一个不引用进来的元素的 index。

subseq 是复制还是引用？复制，这其实是显然的 www 因为从中间抠出来一个子序列，最后一个 cons 元素的 cdr 必须（设置）为 nil，所以有副作用，所以应当是复制。

> (setf x '(1 2 3 4 5))
(1 2 3 4 5)
> (eql (cdr x) (subseq x 1))
NIL ; 复制

reverse 函数返回颠倒的序列。注意，它是引用的！

> (reverse '(A B C))
(C B A)

(defun mirror? (seq) (  ; 可见变量名可以随便玩
    (let ((len (length seq)))
        (and (evenp len);evenp 为偶数谓词（oddp 为奇数谓词）这里似乎直接钦定回文应当是偶数了……罢了
            (let ((mid (/ len 2)))
                (equal (subseq seq 0 mid) (subseq (reverse seq) 0 mid)))))))

**sort **函数。sort 是破坏性的，它有副作用——更改原序列。

> (setf x '(6 3 2 1 4 5))
(6 3 2 1 4 5)
> (sort x #'<) ;comp 参数是必要的
(1 2 3 4 5 6)
> x
(1 2 3 4 5 6) ; 可见 x 的值改变了，不是副本。如果要保留原结果，应当传入副本。

every 和 some 函数接受序列和一个谓词，前者检测是否所有元素都符合谓词，后者则检测是否有些元素符合谓词。

> (every #'oddp '(1 3 5))
T
> (some #'evenp '(1 2 3))
T
> (every #'> '(1 3 5) '(0 2 4)) ; 也可以接受多个序列，此时是比较每一个 nth，如果长度不同，则按最短的那个序列来
T

栈

push 和 pop 函数，再熟悉不过了，要注意的是，它 push 和 pop 在 cons 对象最前而非最后。

(defun my-push (obj stack) (setf stack (cons obj stack)))
(defun my-pop (stack) (let ((top (car stack))) (setf stack (cdr stack)) top))

使用 push 定义 reverse——

(defun my-reverse(lst)
    (let ((res ()))
        (dolist (obj lst)
            (push obj res))
        res))

正如 adjoin 是 cons 的变种，pushnew 是 push 的变种，只有栈中没有该元素才入栈。

点状列表（dotted list）

点状列表就是 cdr 为 atom 且不为 nil 的列表。

> (cons 'a 'b)
(A . B) ; 如此显示

关联列表（assoc-list）

关联列表就像 python 的字典，它容易表示映射（mapping）。它使用点状列表来表示。

assoc 函数用来取……键值对？它也有 key 和 test 参数。同时，也有 assoc-if。

> (setf trans '((+ . "add") (- . "subtract")))
((+ . "add") (- . "subtract"))

> (assoc '+ trans)
(+ . "add")
> (assoc '* trans)
NIL