Scheme 编程/列表操作

列表是 Scheme 中的基本数据结构，就像许多其他函数式编程语言一样。虽然它们是最简单的结构之一，但它们拥有丰富的操作集和惊人的多种用途。在本节中，我们将介绍创建和使用列表的基础知识。

Scheme 列表

列表是元素序列，以 () 结尾，有时称为“空列表”或“nil”。我们可以使用 cons 构建列表，它将新元素附加到列表的头部。

> '()     ; The empty list must be quoted.
()
> (cons 3 '())
(3)
> (cons 2 (cons 3 '()))
(2 3)
> (cons #t (cons 2 (cons 3 '())))
(#t 2 3)

cons 的第一个参数可以是任何 Scheme 对象，第二个参数是列表；(cons x xs) 的值是一个新列表，它包含 x 后跟 xs 中的元素。（Scheme 打印列表的方式使用简写，隐藏了最后的 ()。在上面的响应中，我们只看到括号内的列表元素。）重要的是要注意，我们必须始终引用 ()，以防止 Scheme 尝试将它解释为（无效）表达式。

两个谓词定义了 Scheme 列表类型。null? 对 ()（空列表）为真，其他情况为假，而 pair? 仅对使用 cons 构建的对象返回真。

有两个基本的函数用于访问列表的元素。第一个是 car，它提取列表的第一个元素。

> (car (cons 1 '()))
1
> (car (cons 2 (cons 3 '())))
2
> (car '())
; Error!

将 car 应用于空列表会导致错误。

第二个函数 cdr 给我们提供了列表的尾部：即没有前导元素的列表。

> (cdr (cons 1 '()))
()
> (cdr (cons 2 (cons 3 '())))
(3)
> (cdr '())
; Error!

与 car 一样，尝试将 cdr 应用于空列表会导致错误。

三个函数 cons、car 和 cdr 满足一些有用的恒等式。对于任何 Scheme 对象 x 和列表 xs，我们有

(car (cons x xs)) = x
(cdr (cons x xs)) = xs

对于任何非空列表 ys，我们也有

(cons (car ys) (cdr ys)) = ys

显然，通过连续的 cons 操作构建列表很笨拙。Scheme 提供了内置函数 list，它返回其参数的列表。

> (list 1 2 3 4)
(1 2 3 4)
> (cons 1 (cons 2 (cons 3 (cons 4 '()))))  ; equivalent, but tedious
(1 2 3 4)

list 可以接受任意数量的参数。

我们可以使用 cons、car 和 cdr 编写一系列有用的函数。例如，我们可以定义一个函数来计算列表的长度。

(define (length xs)
  (if (null? xs)
      0
      (+ 1 (length (cdr xs)))))

这个定义，就像大多数列表操作的定义一样，紧密地遵循列表的递归结构。有一个空列表的情况（被分配长度 0），还有一个非空列表的情况（列表尾部的长度加一）。在实践中，Scheme 提供了 length 作为内置函数。

这是一个简单的例子。

(define (find-number n xs)
  (if (null? xs)
      #f
      (if (= n (car xs))
          #t
          (find-number n (cdr xs)))))

find-number 如果参数 n 出现在列表 xs 中，则返回 #t，否则返回 #f。再次，这个定义遵循列表参数的结构。空列表没有元素，所以 (find-number n '()) 总是为假。如果 xs 非空，那么 n 可以是第一个元素，也可以是在尾部的某个地方。在前一种情况下，find-number 立即返回真。在后一种情况下，返回值应该是 n 是否出现在 (cdr xs) 中，如果是则为真，否则为假。但由于这是 find-number 本身的定义，我们有一个新的参数 (cdr xs) 的递归调用。