1. 构造（Conses）
cons真正所做的事情是把两个对象结合成一个具有两部分的对象，称为cons对象。
概念上来说是一对指针，car和cdr。
2. 等式（Equality）
每一次调用cons时，Lisp会配置一块新的内存给两个指针，所以使用通常参数调用cons两次，会产生出两个数值一样的两个对象。
-
eql当两个对象是同一个时才返回真
-equal两个参数的值相同时返回真
3.为什么Lisp没有指针
- 每个值在概念上来说都是一个指针，只不过Lisp不会像C语言那样显示操作指针。
- 程序员可以把任何东西放在任何地方，可以在任何数据结构存放任何类型的对象，包括结构本身。
4. 建立列表（Buiding Lists）
-
copy-list接受一个列表，并返回列表的复本。 -
append返回任何数目列表的串接（concatenation）
5. 存取（Access）
列表中的元素是从0开始编号的
-
nth找到列表特定位置的元素> (nth 0 '(a b c)) A -
nthcdr找到第n个cdr> (nthcdr 2 '(a b c)) (c) -
zerop仅在参数为0时才返回真， nil会报错 -
last返回列表的最后一个cons对象，这与取得最后一个元素不同。
如果你要取得列表的最后一个元素你需要取得last的car。 - Common Lisp第一了从first到tenth这些可以取得列表对应元素的函数。
这些函数不是零索引（zero-indexed） -
cxrCommon Lisp定义了类似caddr这样的函数，表示几个cdr的cdr的car的缩写。
最多四个a或d，不过这样并不易读，所以不推荐。
7. 映射函数（Mapping Functions）
映射函数就是对一个列表中的所有元素做函数调用。
-
mapcar接受一个函数及一个或多个列表，并把函数应用至每个列表的元素中。> (mapcar #'list '(a b c) '(1 2 3 4)) ((A 1) (B 2) (C 3)) -
maplist接受一个函数及一个或多个列表，并将列表cdr后的列表传入函数。> (maplist #'(lambda (x) x) '(a b c)) ((A B C) (B C) (C))
8. 树（Trees）
cons对象可以想象成二叉树，car代表左子树，cdr代表右子树。
操作树的函数通常使用car与cdr同时做递归，这种函数被称为双重递归（diubly recursive）。
9. 理解递归（Understanding Recursion）
检查两件事来判断递归函数是正确的：
- 对长度为0的列表是有效的。
- 给定它对于长度为n的列表是有效的，它对长度是n+1的列表也是有效的。
10. 集合（Sets）
列表是表示小集合的好方法
集合中没有顺序的概念，所以不需要保留元素元素的顺序
-
member接受一个查找的元素和一个被查找的列表，返回找到的元素及之后的元素。
可以接受关键字参数:test和:key -
member-if接受一个函数及一个列表，从第一个被应用函数后返回真的元素位置返回。 -
adjoin接受一个元素和一个列表，如果该元素还不是列表成员，则将其加入列表。 -
union生成并集的函数 -
intersection生成交集的函数 -
set-difference生成补集的函数
11. 序列（Sequences）
一系列有特定顺序的列表。
-
subseq接受三个参数，第一个为列表，第二个为开始截取的位置，第三个为结束的位置，不过为可选的，如果没有第三个参数，则直接截取到列表结尾。 -
reverse返回与参数相同的列表，但顺序不同。 -
sort对传入的列表进行排序，是破坏性的（destructive）即会破坏掉原有的顺序，只可以排序数字。(sort '(0 2 1 3 8) #'>) -
every接受一个判断函数及一个或多个序列（取决于判断函数接受几个参数），所有序列的元素判断为真，则为真> (every #'oddp '(1 3 5)) T -
some接受一个判断函数及一个或多个序列（取决于判断函数接受几个参数），有一个元素判断为真则为真> (some #'evenp '(1 2 3)) T
12. 栈（Stacks）
-
push放入列表前段 -
pop将列表的第一个元素移除，并返回这个元素 -
pushnew宏是push的变种，使用了adjoin而不是cons
13. 点状列表（Dotted Lists）
用点（.）来分割开的列表，称为点状列表。点状列表不是一个正规列表。
点状列表是一个成对的Cons对象，而正规列表不是。
点状列表可以作为类似映射表的方式使用，因为是成对的，而不像正规列表是连接的。
> (setf pair (cons 'a 'b))
(A . B)
14. 关联列表（Assoc-lists）
一个由cons对象组成的列表称之为关联列表（assoc-listor alist）。关联列表很慢，但在初期的程序中使用很方便。
> (setf trans '((+ . "add")))
> (assoc '+ trans)
(+ . "add")
15. 垃圾（Garbages）
列表提供顺序存取而不是随机存取，所以会比数组慢。
Cons对象倾向于用指针表示，所以访问一个列表意味着访问一系列的指针。
虽然这样比简单地像数组一样增加索引值慢，但所话费的代价与配置及回收Cons单元比起来小多了。
垃圾回收可以让程序员不比现实的使用allocate及dellocate进行内存管理，而是由Lisp进行内存管理，这样有效的避免内存泄漏及悬垂指针的问题。
但垃圾回收也是需要代价的。所以如果需要写出高性能的Lisp程序是需要时时考虑对Cons对象的使用，因为Cons对象始终是需要被回收的。
有些Lisp实现回收的Cons代价很大，而有的Lisp实现，内存管理相当好，以至于使用cons比不适用cons更快。
习题（Exercises）
- （a） (cons 'a (cons 'b (cons (cons 'c (cons 'd nil)) nil)))
- （b）(cons 'a (cons (cons 'b (cons (cons 'c (cons (cons 'd nil) nil)) nil)) nil))
- （c）(cons (cons (cons 'a (cons 'b nil)) (cons 'c nil)) (cons 'd nil))
- （d）(cons 'a (cons (cons 'b 'c) (cons 'd nil)))
(defun new-union (lst1 lst2)
(if (null lst2)
lst1
(if (null (member (car lst2) lst1))
(append (new-union lst1 (cdr lst2))
(cons (car lst2) nil))
(new-union lst1 (cdr lst2)))))
(defun occurrences (ls)
(let ((acc nil))
(dolist (obj ls)
(let ((p (assoc obj acc)))
(if p
(incf (cdr p))
(push (cons obj 1) acc))))
(sort acc #'> :key #'cdr)))
因为member使用eql来比较对象
- （a）递归
(defun rec-pos+ (lst) (if (null lst) lst (let* ((lst-pos (- (length lst) 1)) (cur-ele (nth lst-pos lst)) (new-lst '())) (append new-lst (rec-pos+ (remove cur-ele lst)) (cons (+ cur-ele lst-pos) nil))))) - （b）迭代
(defun ite-pos+ (lst) (if (null lst) lst (let ((lst-len (length lst)) (new-lst '())) (progn (do ((i 0 (+ i 1))) ((>= i lst-len) new-lst) (setf new-lst (append new-lst (cons (+ (nth i lst) i) nil)))))))) - （c）mapcar
(defun map-pos+ (lst) (if (null lst) lst (let ((cur-pos 0)) (mapcar #'(lambda (x) (progn (setf x (+ x cur-pos)) (setf cur-pos (+ cur-pos 1)) x)) lst))))
- （a）cons
(defun our-cons (x y)
(let ((ls '(nil .nil)))
(setf (car ls) x
(cdr ls) y)
ls))
- （b）list
(defun our-list (&rest items)
(our-list-0 items))
(defun our-list-0 (lst)
(if lst
(cons (car lst)
(our-list-0 (cdr lst)))))
- （c）length (for lists)
(defun our-length (lst)
(if lst
(+ 1
(our-length (cdr lst)))
0))
- （d）member (for lists; no keywords)
(defun our-member (target lst)
(if lst
(if (eq target (car lst))
lst
(our-member target (cdr lst)))))
(defun n-elts (elt n)
(if (> n 1)
(cons n elt) ;; 将list修改为cons，因为list本身会使用多个cons
elt))
(defun showdots (lst)
(showdots-rec lst 0))
(defun showdots-rec (lst n)
(if lst
(progn
(if (atom (car lst))
(format t "(~A . " (car lst))
(progn
(format t "(")
(showdots-rec (car lst) 0)
(format t " . ")))
(showdots-rec (cdr lst) (+ 1 n)))
(progn
(format t "nil")
(dotimes (j n)
(format t ")")))))
