2.3 列表，迭代与递归
Racket 是 Lisp 语言的一种方言，Lisp 得名于“LISt Processor（列表处理器）”。 内建的列表数据类型即保留了该语言的显著特征。
list 函数接受任意数量的值并返回一个包含这些值的列表：
> (list "red" "green" "blue") '("red" "green" "blue")
> (list 1 2 3 4 5) '(1 2 3 4 5)
列表通常以 ' 打印，不过其打印的形式取决于其内容。 更多信息见 序对与列表。
As you can see, a list result prints in the REPL as a quote ' and then a pair of parentheses wrapped around the printed form of the list elements. There’s an opportunity for confusion here, because parentheses are used for both expressions, such as (list "red" "green" "blue"), and printed results, such as '("red" "green" "blue"). In addition to the quote, parentheses for results are printed in blue in the documentation and in DrRacket, whereas parentheses for expressions are brown.
如你所见，REPL 中列表的打印结果为一个单引号 ' 后跟一对括号括住的列表，列表中的元素则为对应的打印形式。 这里有一点容易混淆的地方：括号被同时用于表达式（如 (list "red" "green" "blue")）和打印结果（如 '("red" "green" "blue")）。 不过在文档和 DrRacket 中，带单引号和括号的打印结果会以蓝色显示， 而表达式中的括号则为棕色。
Racket 中预定义了很多用于操作列表的函数。下面是一些实例：
> (length (list "hop" "skip" "jump")) ; 元素计数 3
> (list-ref (list "hop" "skip" "jump") 0) ; 按位置提取元素 "hop"
> (list-ref (list "hop" "skip" "jump") 1) "skip"
> (append (list "hop" "skip") (list "jump")) ; 连接列表 '("hop" "skip" "jump")
> (reverse (list "hop" "skip" "jump")) ; 反转顺序 '("jump" "skip" "hop")
> (member "fall" (list "hop" "skip" "jump")) ; 查找成员 #f
2.3.1 预定义的列表循环
除了像 append 这样的简单操作外，Racket 中还包含一些用于迭代列表元素的函数。 迭代函数所扮演的角色类似于 Java、Racket 和其它语言中的 for 语句。 由于 Racket 迭代的主体被封装成了应用到每个元素的函数，因此 lambda 形式与迭代函数的组合会特别方便。
不同的列表迭代函数会以不同的方式组合迭代结果。map 函数会使用所有元素的结果创建一个新的列表：
> (map sqrt (list 1 4 9 16)) '(1 2 3 4)
> (map (lambda (i) (string-append i "!")) (list "peanuts" "popcorn" "crackerjack")) '("peanuts!" "popcorn!" "crackerjack!")
andmap 和 ormap 函数会通过连续应用 and 或 or 组合出结果：
> (andmap string? (list "a" "b" "c")) #t
> (andmap string? (list "a" "b" 6)) #f
> (ormap number? (list "a" "b" 6)) #t
map、andmap 和 ormap 函数不仅能处理单个列表， 还可以处理多个列表。这些列表的长度必须相同，且给定的函数必须对每个列表接受一个元素：
> (map (lambda (s n) (substring s 0 n)) (list "peanuts" "popcorn" "crackerjack") (list 6 3 7)) '("peanut" "pop" "cracker")
filter 函数会保留主体中结果为真的元素，并丢弃主体中结果为 #f 的元素：
> (filter string? (list "a" "b" 6)) '("a" "b")
> (filter positive? (list 1 -2 6 7 0)) '(1 6 7)
foldl 函数推广了某些迭代函数。它使用一个应用于每个元素 elem 的函数来处理元素，并将其结果与“当前值” v 相结合，因此应用于每个元素的函数需要一个额外的第一项参数。 此外，初始的“当前值”必须在列表之前提供：
译注：foldl 的参数分为三部分：第一部分为一个过程 proc，其参数个数等于要迭代的列表个数加一；第二部分为环境中初始的“当前值” init；第三部分是一个或多个等长的列表 lst ...+。在本例中， 匿名函数的第一个参数 elem 会在每次迭代时绑定到列表中的每个元素， 而最后一个参数 v 则总是会绑定到“当前值”；待第一次迭代结束后， 匿名函数的返回值则作为下一次迭代的当前函数，以此类推。 将“当前值”绑定到匿名函数中最后一个参数的做法叫做递延式（Continuation-Passing Style，旧译为“延续传递风格”）。 —————Oling Cat
> (foldl (lambda (elem v) (+ v (* elem elem))) 0 '(1 2 3)) 14
尽管 foldl 很通用，但它并没有其它函数那么常用。一个原因是 map、ormap、andmap 和 filter 已经覆盖了最常见的几种列表循环。
Racket 提供了一种通用的列表推导形式 for/list， 它会通过对序列进行迭代来构建出一个列表。列表推导以及相关的迭代形式见 Iterations and Comprehensions。
2.3.2 从零开始构造列表迭代
尽管 map 与其它迭代函数是预定义的，然而它们却并不是原语（Primitive） 因而也没什么趣味。你可以只用很少几个列表的原语就能写出等价的迭代。
由于 Racket 的列表是一个链表，而非空列表的两个核心操作为：
要为链表创建一个新的节点—
> empty '()
> (cons "head" empty) '("head")
> (cons "dead" (cons "head" empty)) '("dead" "head")
要处理一个列表，你需要能够区分空列表和非空列表，因为 first 和 rest 只能作用于非空列表。empty? 函数能够检测非空列表：
> (empty? empty) #t
> (empty? (cons "head" empty)) #f
> (cons? empty) #f
> (cons? (cons "head" empty)) #t
通过这些代码片段，你可以写出自己的 length 和 map 等函数。
(define (my-map f lst) (cond [(empty? lst) empty] [else (cons (f (first lst)) (my-map f (rest lst)))]))
> (my-map string-upcase (list "ready" "set" "go")) '("READY" "SET" "GO")
如果以上派生定义对你而言有些难以理解，可以阅读 How to Design Programs《程序设计方法》。 如果你只是对用递归调用而非循环构造感到疑惑的话，请继续往后阅读。
2.3.3 尾递归
对于长度为 n 的列表来说，函数 my-length 和 my-map 均会在 O(n) 的空间中运行。我们只需通过想象就能明白 (my-length (list "a" "b" "c")) 的求值方式：
(my-length (list "a" "b" "c")) = (+ 1 (my-length (list "b" "c"))) = (+ 1 (+ 1 (my-length (list "c")))) = (+ 1 (+ 1 (+ 1 (my-length (list))))) = (+ 1 (+ 1 (+ 1 0))) = (+ 1 (+ 1 1)) = (+ 1 2) = 3
对于包含 n 个元素的列表来说，求值会在栈中堆叠 n 次加法， 直到列表被用尽后才把它们加起来。
你可以通过一路求和来避免加法的堆积。为了按这种方式来累积长度， 我们需要一个函数来接受一个列表和目前已知的长度。以下代码中使用了局部函数 iter 在其参数 len 中累积长度：
(define (my-length lst) ; local function iter: (define (iter lst len) (cond [(empty? lst) len] [else (iter (rest lst) (+ len 1))])) ; body of my-length calls iter: (iter lst 0))
现在的求值过程如下：
(my-length (list "a" "b" "c")) = (iter (list "a" "b" "c") 0) = (iter (list "b" "c") 1) = (iter (list "c") 2) = (iter (list) 3) 3
修订后的 my-length 会在常量空间内运行，正如上面求值步骤所示。 也就是说，如果一个函数调用的结果（(iter (list "b" "c") 1)） 刚好为另一个函数调用的结果（(iter (list "c") 2)）， 那么第一个函数无需等待第二个函数返回，不然会浪费空间。
这种求值行为有时被称作尾递归优化。不过它在 Racket 中不仅是一种“优化”，还是一种对代码运行方式的保证。更确切地说， 尾部的表达式相对于下一次迭代的尾部表达式来说， 并不会占用额外的计算空间。
在 my-map 的例子中，O(n) 的空间复杂度是合理的， 因为它必须生成一个大小为 O(n) 的结果。不过， 你可以通过累积结果列表来消除常量因子。唯一的问题是累积的列表是反向的， 因此你最后还要将它再反转过来：
如下面所述，试图像这样减少常量因子通常并不值得。
(define (my-map f lst) (define (iter lst backward-result) (cond [(empty? lst) (reverse backward-result)] [else (iter (rest lst) (cons (f (first lst)) backward-result))])) (iter lst empty))
事实证明，如果将它这样写：
(define (my-map f lst) (for/list ([i lst]) (f i)))
那么该函数中的 for/list 形式展开后的代码，本质上和局部定义并使用 iter 是一样的，区别只是语法上更加方便而已。
2.3.4 递归与迭代
示例 my-length 和 my-map 表明迭代只是递归的一种特例。 在很多语言中，将计算尽可能写成迭代的形式是十分重要的，否则性能就会变差， 即便不太大的输入也会导致栈溢出。在 Racket 中，当计算易于在常量空间内执行时， 使用尾递归来避免 O(n) 的空间消耗有时也是十分重要的。
与此同时，在 Racket 中递归并不会导致特别差的性能，并且也没有栈溢出这类的事情。 如果计算涉及了太多上下文，那么可能会耗尽内存。不过比起其它会触发栈溢出的语言来， Racket 通常需要高几个数量级的深度递归才能耗尽内存。由于尾递归程序的运行与循环如出一辙， 再综合以上因素考虑，通常 Racket 程序员会接受递归而非避免它们。
例如，假设你想从一个列表中移除连续的重复项。虽然此函数可以写成循环的形式， 即在每次迭代时记录上一个元素，不过 Racket 程序员会更倾向于写成如下形式：
(define (remove-dups l) (cond [(empty? l) empty] [(empty? (rest l)) l] [else (let ([i (first l)]) (if (equal? i (first (rest l))) (remove-dups (rest l)) (cons i (remove-dups (rest l)))))]))
> (remove-dups (list "a" "b" "b" "b" "c" "c")) '("a" "b" "c")
通常，此函数会为长度为 n 的输入消耗 O(n) 的空间， 不过这没什么问题，因为它会产生一个 O(n) 的结果。 如果输入的列表中大部分元素都是重复的，那么其结果列表会比 O(n) 更小，自然 remove-dups 占用的空间也会更少。原因是当函数丢弃重复项时， 它会直接返回调用 remove-dups 的结果，因此也就产生了尾调用“优化”的效果：
(remove-dups (list "a" "b" "b" "b" "b" "b")) = (cons "a" (remove-dups (list "b" "b" "b" "b" "b"))) = (cons "a" (remove-dups (list "b" "b" "b" "b"))) = (cons "a" (remove-dups (list "b" "b" "b"))) = (cons "a" (remove-dups (list "b" "b"))) = (cons "a" (remove-dups (list "b"))) = (cons "a" (list "b")) = (list "a" "b")