列表操作与高阶函数

列表操作

Racket 为列表提供了好用的内置过程：

list-ref

list-ref 接受一个列表和一个数字 n，返回列表的第 n 项。列表的第一个元素索引为 0，即它是列表的第 0 个元素。下面是 list-ref 的定义：

(define (list-ref lst n)
  (if (= n 0)
      (car lst)
      (list-ref (cdr lst) (- n 1))))

下面是它如何工作的例子：

-> (define squares (list 1 4 9 16 25))
squares
-> (list-ref squares 3)
16

null?

null? 接受一个列表作为实参，如果列表为空则返回 #t，否则返回 #f：

(null? (list 1 3))
#f

(null? '())
#t

length

length 接受一个列表作为实参，返回列表中元素的个数。下面是 length 的定义：

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

例子：

-> (define odds (list 1 3 5 7))
odds
-> (length odds)
4

列表与高阶函数

从现在开始，我们将主要使用列表和序对，而不是句子。这很好，因为这意味着我们能更仔细地观察 Racket 如何表示数据。但这也意味着，我们之前用句子定义的许多重要高阶函数，现在必须重写以适配序对。

every 与 map

回顾一下高阶函数 every：它接受一个函数和一个句子，返回把该函数应用到句子每个元素后的句子。用序对实现等价功能的高阶函数叫 map（映射），它接受一个函数和一个列表，返回把该函数映射到列表每个元素后的列表。map 是递归定义的函数，如下所示：

(define (map proc items)
  (if (null? items)
      null
      (cons (proc (car items))
            (map proc (cdr items)))))

列表的 null? 过程类似于句子的 empty? 过程，用于检查给定实参是否为空列表。下面是几个 map 调用示例：

-> (map square (list 1 2 3 4 5))
(1 4 9 16 25)
-> (map car (list (cons 1 2) (cons 3 4) (cons 5 6)))
(1 3 5)

keep 与 filter

我们在作业 2 的 filtered-accumulate 问题中已经瞥见过 filter，所以你对高阶函数 filter 的作用应该已有概念。filter（过滤）接受两个实参——一个谓词（predicate）和一个列表，返回只含满足谓词元素的列表。看看正式定义：

(define (filter pred lst)
  (cond ((null? lst) null)
        ((pred (car lst))
          (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

一些例子：

-> (filter odd? '(1 2 3 4 5))
(1 3 5)
-> (filter (lambda (x) (> x 2)) '(1 2 3 4 5))
(3 4 5)

accumulate

最后是句子的 accumulate 过程。它接受一个双参函数、一个基值和一个句子，用这个运算不断组合列表中的值，并以基值结束/开始。列表中有两个与 accumulate 等价的过程：foldl 和 foldr。两者都接受一个双参函数、一个基值和一个列表。

fold-left（即 foldl）从列表最后一个（最右）元素开始，不断递归应用该函数，直到到达列表的第一个元素。因此它向左折叠。例如，下面是求值 foldl 调用的步骤：

-> (foldl cons '() '(1 2 3 4))
... (cons 4 (cons 3 (cons 2 (cons 1 '()))))
(4 3 2 1)

再看一个例子：

-> (define combiner (lambda (x y) (cons (add1 x) y)))
combiner
(foldl combiner '() '(1 2 3 4))
... (combiner 4 (combiner 3 (combiner 2 (combiner 1 '()))))
... (5 . (4 . (3 . (2 . ()))))
(5 4 3 2)

另一方面，fold-right（即 foldr）从列表第一个（最左）元素开始，不断递归应用该函数，直到到达列表的最后一个元素。因此它向右折叠。看看这些调用：

-> (foldr cons '() '(1 2 3 4))
... (cons 1 (cons 2 (cons 3 (cons 4 '()))))
(1 2 3 4)

-> (foldr + 0 '(1 2 3 4))
... (+ 1 (+ 2 (+ 3 (+ 4 0))))
10

现在我们有了两个版本的 accumulate。只有当组合函数的实参顺序会影响结果时，foldl 和 foldr 的值才会不同。

高阶函数小结

为了让过渡更容易，下面用一张表展示句子上的操作及其在列表上的等价操作。

句子	列表
se/sentence	cons/list/append
first	car
bf/butfirst	cdr
last	无等价操作
bl/butlast	无等价操作
count	length
item（从 1 开始计数）	list-ref（从 0 开始计数）
every	map
keep	filter
accumulate	foldl/foldr