4.4 序列 (Sequences)

在 Common Lisp 里，序列类型包含了列表与向量（因此也包含了字符串）。有些用在列表的函数，实际上是序列函数，包括 remove 、 length 、 subseq 、 reverse 、 sort 、 every 以及 some 。所以 46 页（译注 3.11 小节的 mirror? 函数）我们所写的函数，也可以用在其他种类的序列上：

  1. > (mirror? "abba")
  2. T

我们已经看过四种用来取出序列元素的函数： 给列表使用的 nth ， 给向量使用的 aref 及 svref ，以及给字符串使用的 char 。 Common Lisp 也提供了通用的 elt ，对任何种类的序列都有效：

  1. > (elt '(a b c) 1)
  2. B

针对特定类型的序列，特定的存取函数会比较快，所以使用 elt 是没有意义的，除非在代码当中，有需要支持通用序列的地方。

使用 elt ，我们可以写一个针对向量来说更有效率的 mirror? 版本：

  1. (defun mirror? (s)
  2.   (let ((len (length s)))
  3.     (and (evenp len)
  4.          (do ((forward 0 (+ forward 1))
  5.               (back (- len 1) (- back 1)))
  6.              ((or (> forward back)
  7.                   (not (eql (elt s forward)
  8.                             (elt s back))))
  9.               (> forward back))))))

这个版本也可用在列表，但这个实现更适合给向量使用。频繁的对列表调用 elt 的代价是昂贵的，因为列表仅允许顺序存取。而向量允许随机存取，从任何元素来存取每一个元素都是廉价的。

许多序列函数接受一个或多个，由下表所列的标准关键字参数：

参数用途缺省值
:key应用至每个元素的函数identity
:test作来比较的函数eql
:from-end若为真，反向工作。nil
:start起始位置0
:end若有给定，结束位置。nil

一个接受所有关键字参数的函数是 position ，返回序列中一个元素的位置，未找到元素时则返回 nil 。我们使用 position 来演示关键字参数所扮演的角色。

  1. > (position #\a "fantasia")
  2. 1
  3. > (position #\a "fantasia" :start 3 :end 5)
  4. 4

第二个例子我们要找在第四个与第六个字符间，第一个 a 所出现的位置。 :start 关键字参数是第一个被考虑的元素位置，缺省是序列的第一个元素。 :end 关键字参数，如果有给的话，是第一个不被考虑的元素位置。

如果我们给入 :from-end 关键字参数，

  1. > (position #\a "fantasia" :from-end t)
  2. 7

我们得到最靠近结尾的 a 的位置。但位置是像平常那样计算；而不是从尾端算回来的距离。

:key 关键字参数是序列中每个元素在被考虑之前，应用至元素上的函数。如果我们说，

  1. > (position 'a '((c d) (a b)) :key #'car)
  2. 1

那么我们要找的是，元素的 car 部分是符号 a 的第一个元素。

:test 关键字参数接受需要两个实参的函数，并定义了怎样是一个成功的匹配。缺省函数为 eql 。如果你想要匹配一个列表，你也许想使用 equal 来取代：

  1. > (position '(a b) '((a b) (c d)))
  2. NIL
  3. > (position '(a b) '((a b) (c d)) :test #'equal)
  4. 0

:test 关键字参数可以是任何接受两个实参的函数。举例来说，给定 < ，我们可以询问第一个使第一个参数比它小的元素位置：

  1. > (position 3 '(1 0 7 5) :test #'<)
  2. 2

使用 subseq 与 position ，我们可以写出分开序列的函数。举例来说，这个函数

  1. (defun second-word (str)
  2.   (let ((p1 (+ (position #\  str) 1)))
  3.     (subseq str p1 (position #\  str :start p1))))

返回字符串中第一个单字空格后的第二个单字：

  1. > (second-word "Form follows function")
  2. "follows"

要找到满足谓词的元素，其中谓词接受一个实参，我们使用 position-if 。它接受一个函数与序列，并返回第一个满足此函数的元素：

  1. > (position-if #'oddp '(2 3 4 5))
  2. 1

position-if 接受除了 :test 之外的所有关键字参数。

有许多相似的函数，如给序列使用的 member 与 member-if 。分别是， find （接受全部关键字参数）与 find-if （接受除了 :test 之外的所有关键字参数）：

  1. > (find #\a "cat")
  2. #\a
  4. > (find-if #'characterp "ham")
  5. #\h

不同于 member 与 member-if ，它们仅返回要寻找的对象。

通常一个 find-if 的调用，如果解读为 find 搭配一个 :key 关键字参数的话，会显得更清楚。举例来说，表达式

  1. (find-if #'(lambda (x)
  2.              (eql (car x) 'complete))
  3.          lst)

可以更好的解读为

  1. (find 'complete lst :key #'car)

函数 remove （22 页）以及 remove-if 通常都可以用在序列。它们跟 find 与 find-if 是一样的关系。另一个相关的函数是 remove-duplicates ，仅保留序列中每个元素的最后一次出现。

  1. > (remove-duplicates "abracadabra")
  2. "cdbra"

这个函数接受前表所列的所有关键字参数。

函数 reduce 用来把序列压缩成一个值。它至少接受两个参数，一个函数与序列。函数必须是接受两个实参的函数。在最简单的情况下，一开始函数用序列前两个元素作为实参来调用，之后接续的元素作为下次调用的第二个实参，而上次返回的值作为下次调用的第一个实参。最后调用最终返回的值作为 reduce 整个函数的返回值。也就是说像是这样的表达式：

  1. (reduce #'fn '(a b c d))

等同于

  1. (fn (fn (fn 'a 'b) 'c) 'd)

我们可以使用 reduce 来扩充只接受两个参数的函数。举例来说，要得到三个或多个列表的交集(intersection)，我们可以：

  1. > (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
  2. (A)