列表

2016-12-18 本文已影响0人 Saru様

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 ")")))))

列表