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) 的遞迴呼叫。