列表——Racket 的主力数据结构

在 Racket 里，列表不是数组，而是一个个 cons 单元串成的链——理解了这根链，first、rest、map、filter 才算有了根。

你已经会用括号写表达式，也认得 Racket 的数、字符串、布尔。但真要写点有用的程序，绕不开一类数据：一堆东西排成一排——一组温度读数、一串文件名、几个待处理的请求。

多数语言里这东西叫数组，按下标随机存取，瞬间到位。Racket 的主力不是数组，是列表。列表看起来也像“一排东西”，骨子里却是另一回事。这篇讲清楚列表到底是什么，怎么造、怎么拆、怎么用。

先说结论：列表是一条 cons 链，链的尽头是空表 '()。记住这一句，后面所有的操作都是在拆或拼这根链。

cons：两个值，粘成一格

列表的原子不是“列表”，是 pair（对）。cons 接受两个值，把它们粘成一个 pair——第一个值放左格，第二个值放右格。

(cons 1 2)
;; '(1 . 2) 注意中间那个点：左格是 1，右格是 2

(car (cons 1 2))
;; 1 car 取左格

(cdr (cons 1 2))
;; 2 cdr 取右格

那个点 . 是 pair 的标志，提醒你这个 pair 还不是 list。car 和 cdr 这两个名字古怪，它们是 1958 年 Lisp 在 IBM 704 上的硬件遗留（地址寄存器 / 减量寄存器），全 Lisp 族都这么叫，认了就行。

cons 只做一件事：把两个值粘成一个格子，至于格子怎么用，它不管。

list：把 cons 串成一条链

一个 pair 装两个东西。要装一串，就把第二个格子里再放一个 pair，一层层套下去，最里面那个 pair 的右格放一个特殊值表示“到此为止”——这个值就是空表 '()。

(cons 1 (cons 2 (cons 3 '())))
;; '(1 2 3)

结果里没有点了：当一条 cons 链的右格最终通向 '()，它就是一个 list。cons 1 2 是 pair 不是 list，cons 1 (cons 2 '()) 才是。

'(1 2 3) 拆开看，是三个 cons 单元手拉手：

每个 cons 格子分两半：左半放元素，右半是指针，指向下一个格子。最后一个格子的指针指向 '()，链就到头了。

手写三层 cons 太累，Racket 给了两个快捷方式。list 把参数一个个排好：

(list 1 2 3)
;; '(1 2 3)

(list "a" "b" "c")
;; '("a" "b" "c")

另一个是 quote，在括号前加一个 '，Racket 就把括号里的结构原样当数据，不去求值。两者结果常常一样，但有个关键区别——list 的参数会先求值，quote 不会：

(list 1 (+ 1 1) 3)
;; '(1 2 3) 元素先求值，再装进列表

'(1 (+ 1 1) 3)
;; '(1 (+ 1 1) 3) quote 不求值，原样保留

写练习、写测试数据用 '(...) 最省事；元素需要先算出来再组装时，用 list。

'() 是空表，也是这根链的地基。判断一个值是不是空表，用 null?，或它的同义词 empty?：

(null? '())
;; #t

(empty? '())
;; #t

(null? '(1 2 3))
;; #f

列表不是数组，是一条 cons 链，链的尽头是空表 '()。 这一区别决定后面的一切：访问元素靠“顺着链走”，不是“按下标跳”。

取头取尾：car/cdr 与 first/rest

既然列表是 cons 链，取第一个元素就是取最外层 pair 的左格，取“剩下的”就是取它的右格——还是 car 和 cdr：

(car '(1 2 3))
;; 1

(cdr '(1 2 3))
;; '(2 3)

car/cdr 是 pair 级别的操作，对任何 pair 都能用。但读列表代码时，这两个古词实在不友好，Racket 给了两个更贴列表的别名：first 取第一个，rest 取剩下的。

(first '(1 2 3))
;; 1

(rest '(1 2 3))
;; '(2 3)

first 和 rest 做的事与 car、cdr 一模一样，区别只在名字和态度：一眼就看出在处理列表，不用记硬件缩写。

处理列表时用 first/rest，处理裸 pair 时才回到 car/cdr。

一个直觉值得建立：对任何非空列表，first 给你一个元素，rest 给你一个更短的列表。短到只剩一个元素时，rest 就是 '()。这条直觉是后面递归的根。

四个常用操作：length、reverse、append、list-ref

日常处理列表，有四个函数最常用。length 数长度，reverse 翻过来，append 把几条列表拼成一条：

(length '(1 2 3 4))
;; 4

(reverse '(1 2 3))
;; '(3 2 1)

(append '(1 2) '(3 4) '(5))
;; '(1 2 3 4 5)

append 能接任意多个列表，按顺序首尾相连。

取指定位置的元素用 list-ref。这里有个从数组过来的人最容易踩的坑：

(list-ref '(a b c d) 0)
;; 'a

(list-ref '(a b c d) 2)
;; 'c

list-ref 从 0 开始数——(list-ref lst 0) 是第一个，(list-ref lst 2) 是第三个。但更要紧的是它怎么拿到那个元素：没有“下标直达地址”的快车，只能从链头开始，走一步 cdr、再走一步，走 n 步才到。代价和下标 n 成正比，不是数组那种 O(1)。

list-ref 从 0 开始数，而且不是瞬间拿到——它要顺着链走 n 步。 这是“列表是链”的直接代价。如果你发现自己频繁随机访问某个位置，那该用的不是列表，是 Racket 的 vector。

嵌套列表：表里有表

列表的元素可以是任何值，包括另一个列表。一个二维的例子：

'((1 2) (3 4) (5))
;; '((1 2) (3 4) (5))

这是一条三个元素的列表，每个元素本身又是一条列表。first 取第一格，得到的是第一个子列表：

(first '((1 2) (3 4) (5)))
;; '(1 2)

(rest '((1 2) (3 4) (5)))
;; '((3 4) (5))

要取第二个子列表里的头，就 rest 往后走一步、再 first 取头：

(first (rest '((1 2) (3 4) (5))))
;; '(3 4)

嵌套列表本质还是 cons 链，只是链上某些格子装的不是数，而是另一条链。树形数据、配置结构、S-表达式都长这样——这也是 Racket 把“代码即数据”玩得转的底层原因。

用递归处理列表

回头看列表的定义：一个列表，要么是空表 '()，要么是一个 pair——左格装第一个元素，右格装剩下的列表。这个定义本身就是递归的，列表由更短的列表组成。

所以处理列表最自然的写法就是递归：空表怎么办（base case），非空表就用 first 处理头、把 rest 交给下一层。一个求和的例子：

(define (sum lst)
 (if (empty? lst)
 0
 (+ (first lst) (sum (rest lst)))))

(sum '(1 2 3 4))
;; 10

空表的和是 0；非空表，就把第一个元素加上“剩下的求和”。函数的形状和列表的形状一一对应。

再写一个，把列表里每个元素翻倍：

(define (double-all lst)
 (if (empty? lst)
 '()
 (cons (* 2 (first lst)) (double-all (rest lst)))))

(double-all '(1 2 3))
;; '(2 4 6)

base case 返回空表；非空表，把第一个元素翻倍，再用 cons 接到“剩下的翻倍”前面。新列表是边递归边 cons 出来的。

列表的形状是递归的，所以处理列表的函数也自然是递归的。 你会发现，“对每个元素做同一件事”这类需求，递归写法长得几乎一样——换个处理头的操作、换个 base case 的值而已。

这种重复，正是下一章要替你封装的东西。“对每个元素做同一件事”有个现成的名字叫 map，“挑出满足条件的元素”叫 filter。它们把递归的骨架包好了，你只管告诉它“做什么”。下一篇《告别循环》，拆这两个高阶函数。

列表是一条 cons 链，空表 '() 是地基，递归是它的母语。下一章的 map、filter，不过是这套递归的现成封装。