ANSI Common Lisp 学习笔记 第三章

scinart posted @ 2013年4月26日 23:51 in Lisp , 1698 阅读

* 第三章:列表
** #'eql and #'equal 每一次你调用 cons 时, Lisp 会配置一块新的内存给两个指针。所以如果我们用同样的参数调用 cons 两次,我们得到两个数值看起来一样,但实际上是两个不同的对象:

(eql (cons 'a nil) (cons 'a nil))

NIL


如果我们也可以询问两个列表是否有相同元素,那就很方便了。 Common Lisp 提供了这种目的另一个判断式: equal 。而另一方面 eql 只有在它的参数是相同对象时才返回真,

(setf x (cons 'a nil))
(A)
(eql x x)

T
本质上 equal 若它的参数打印出的值相同时,返回真:

(equal x (cons 'a nil))

T
** #'copy-list 函数 copy-list 接受一个列表,然后返回此列表的复本。新的列表会有同样的元素,但是装在新的 Cons 对象里 这个定义暗示着 x 与 (copy-list x) 会永远 equal ,并永远不 eql ,除非 x 是 NIL 。
** #'append

(setf x '(a b) y '(c d) z 'e)
(setf app (append x y z))
(setf (car x) 'aa)

app

(setf z 'ee)

app ;; 这里Clozure和Paul Graham的实现不太一样。
** #'nth zero-indexed
** #'nthcdr zero-indexed
** #'zerop
** #'last 函数 last 返回列表的最后一个 Cons 对象
** #'first second ... Common Lisp 定义了函数 first 直到 tenth 可以取得列表对应的元素。这些函数不是零索引的
** #'cadr ... Common Lisp 定义了像是 caddr 这样的函数,它是 cdr 的 cdr 的 car 的缩写 ( car of cdr of cdr )。所有这样形式的函数 cxr ,其中 x 是一个字串,最多四个 a 或 d
** #'mapcar Common Lisp 提供了数个函数来对一个列表的元素做函数调用。最常使用的是 mapcar ,接受一个函数以及一个或多个列表,并返回把函数应用至每个列表的元素的结果,直到有的列表没有元素为止 #+ example:

(mapcar #'list '(a b c d)
               '(1 2 3)
               '(α β γ))

** #'copy-tree and #'copy-list

(setf a '(1 2 3))
(setf b '(4 5 6))
(setf c 'c)
(setf l1 (list a b c))
(setf l2 (copy-list l1))
(setf l3 (copy-tree l1))

(setf (car a) 0)
(setf (car b) 0)
(setf c 'd)

l1 l2 l3

(setf (caddr l1) 'D)

l1 l2 l3

((0 2 3) (4 5 6) C)
((0 2 3) (4 5 6) C)
((1 2 3) (4 5 6) C)

;deep copy

((0 2 3) (0 5 6) D)
((0 2 3) (0 5 6) C)
((1 2 3) (4 5 6) C)

** #'integerp
** #'member and #'member-if

(member '(a) '((a) (z)) :test #'equal)
(member 'a '((a b) (c d)) :key #'car)
(member-if #'oddp '(2 3 4))

** #'adjoin #'union #'intersection #'set-difference 函数 adjoin 像是条件式的 cons 。它接受一个对象及一个列表,如果对象还不是列表的成员,才构建对象至列表上。

(adjoin 'b '(a b c))
(adjoin 'z '(a b c))
(union '(a b c q) '(c b t s))
(intersection '(a b c) '(b b c))
(set-difference '(a b c d e) '(b e))

** #'length #'subseq #'reverse

(length '(a b c))
(subseq '(a b c d) 1 3)
(reverse '(a b c))

** #'sort : destructive

(sort '(0 2 1 3 8) #'<)

** #'every and #'some 如果它们输入多于一个序列时,判断式必须接受与序列一样多的元素作为参数,而参数从所有序列中一次提取一个

(every #'oddp '(1 3 5))
(some #'evenp '(1 2 3))
(every #''(1 3 5) '(0 2 4))

** #'push #'pop and #'pushnew (macro) 用 Cons 对象来表示的列表,很自然地我们可以拿来实现下推栈 (pushdown stack)。这太常见了,以致于 Common Lisp 提供了两个宏给堆叠使用: (push x y) 把 x 放入列表 y 的前端。而 (pop x) 则是将列表 x 的第一个元素移除,并返回这个元素。 pushnew 宏是 push 的变种,使用了 adjoin 而不是 cons #+example

(let ((x '(a b)))
     (pushnew 'c x)
     (pushnew 'a x)
     x)

** Assoc-lists 用 Cons 对象来表示映射 (mapping)也是很自然的。一个由 Cons 对象组成的列表称之为关联列表(assoc-listor alist)。这样的列表可以表示一个翻译的集合,举例来说:

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

关联列表很慢,但是在初期的程序中很方便。 Common Lisp 有一个内置的函数 assoc ,用来取出在关联列表中,与给定的键值有关联的 Cons 对:

(assoc '+ trans)
(assoc '* trans)

** TODO 3.15 Example: Shortest Path
** Exercise
*** 1 omitted
*** 2 写一个保留原本列表中元素顺序的 union 版本:

(defun new-union (la lb)
  (reverse (union lb (reverse la))))

;; 一次成功,耶

(new-union '(a b c) '(b a d))

*** 3 定义一个函数,接受一个列表并返回一个列表,指出相等元素出现的次数,并由最常见至最少见的排序: ;; cond version, more compact.

(defun occurrences (lst)
  (labels ((insert (mem array)
		   (let ((result (member mem array :key #'car)))
		     (cond (result (incf (cdar result)) array)
			   (t (push (cons mem 1) array)))))
	   (occurrences-aid (lst array)
			    (if (null lst)
				(sort array #'(lambda (a b) ((cdr a) (cdr b))))
			      (let ((new-array (insert (car lst) array)))
				(occurrences-aid (cdr lst) new-array)))))
    (occurrences-aid lst nil)))
(occurrences '(a b a d a c d c a))

;; if version, original one.

(defun occurrences (lst)
  (labels ((insert (mem array)
		   (let ((result (member mem array :key #'car)))
		     (if result
			 (progn
			   (incf (cdar result))
			   array)
		       (push (cons mem 1) array))))
	   (occurrences-aid (lst array)
			    (if (null lst)
				(sort array #'(lambda (a b) ((cdr a) (cdr b))))
			      (let ((new-array (insert (car lst) array)))
				(occurrences-aid (cdr lst) new-array)))))
    (occurrences-aid lst nil)))
(occurrences '(a b a d a c d c a))

*** 4 为什么 (member '(a) '((a) (b))) 返回 nil?
*** 5 假设函数 pos+ 接受一个列表并返回把每个元素加上自己的位置的列表:

(pos+ '(7 5 1 4))
(7 6 3 7)

使用 (a) 递归 (b) 迭代 (c) mapcar 来定义这个函数。 ;(a)

(defun pos+ (lst)
  (if (null lst)
      nil
    (cons (car lst)
	  (pos+ (mapcar #'(lambda (x) (incf x)) (cdr lst))))))

;(b)

(defun pos+ (lst &optional (pos 0))
  (if (null (nth pos lst))
      lst
    (progn (incf (nth pos lst) pos)
	   (pos+ lst (+ 1 pos)))))

;(c)

(defun pos+ (lst)
  (let ((pos -1))
    (mapcar #'(lambda (n) (incf pos) (incf n pos)) lst)))

*** 6 略
*** 7 略
*** 8 定义一个函数,接受一个列表并用点状表示法印出

(defun showdots (lst &optional (output-target t))
  "if t then print else return the string"
  (if (null lst)
      "NIL"
    (format output-target
	    "(~A . ~A)"
	    (car lst)
	    (showdots (cdr lst) nil))))

;(showdots '(a b c) t) ;(showdots '(a b c) nil)

(showdots '(a b c))

*** 9 略


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter