Lab 9：Scheme 与 Scheme 列表ok 17 项通过

0. 这份作业在练什么

这是整门课里第一份不用 Python 写的作业。你打开 lab09.scm，看到的是一堆括号， 第一反应通常是「我不会了」。但真相是：这份 lab 里六道题，考的东西你在第 5 到第 12 讲之间 全部学过——分支、高阶函数（higher-order function）、返回函数的函数、链表（linked list）递归。 换的只有写法，没换规则。

所以这份解析的重点不是教你背 Scheme 语法表，而是每道题都问同一个问题： 解释器（interpreter）拿到这个表达式之后，一步一步做了什么？ 只要你能把求值过程说出口，括号写在哪就不再是问题。

做之前应该已经掌握的

1. Over or Under（over-or-under）

题目要什么

写一个过程 over-or-under，收两个数 num1、num2，返回：

• num1 < num2 时返回 -1
• num1 = num2 时返回 0
• num1 > num2 时返回 1

官方测试文件 tests/over_or_under.py 里给的三个用例是：

scm> (over-or-under 5 5)
0
scm> (over-or-under 5 4)
1
scm> (over-or-under 3 5)
-1

翻译成人话：这就是三路比较（three-way comparison），Python 里你会写

def over_or_under(num1, num2):
    if num1 < num2:
        return -1
    elif num1 == num2:
        return 0
    else:
        return 1

边界情况其实只有一个值得留意：三个分支必须互斥且穷尽。 两个数比较只有小于、等于、大于三种可能，没有第四种，所以最后一路可以放心用 else 兜底，不必再写一次 (> num1 num2)。题目还额外提醒了一句： 在 Scheme 里 (0) 会报错，因为括号意味着「调用 0 这个过程」。这句提醒不是废话—— 初学者最爱写 (cond ((< num1 num2) (-1)) ...)，多套一层括号，直接崩。

怎么想到的

拦住人的从来不是逻辑，是「比较怎么写」和「分支怎么写」。逐个拆。

代码

(define (over-or-under num1 num2)
  ; cond 从上到下逐个检查条件，命中就返回对应的值
  (cond ((< num1 num2) -1)
        ((= num1 num2) 0)
        (else 1)))

逐行看：

验证：手工追踪 (over-or-under 3 5)

(over-or-under 3 5)

1. 这是调用表达式。先求算子 over-or-under
   → 全局帧里查到一个过程对象，形参 (num1 num2)
2. 从左到右求算子数：3 → 3，5 → 5
3. apply：新建一帧 f1，parent = 全局，绑定 num1 = 3、num2 = 5
   在 f1 中求值过程体 (cond ...)

4. cond 是特殊形式，不会先算所有子表达式，而是逐句试：
   子句 1：求谓词 (< num1 num2) = (< 3 5) → #t
           #t 不是 #f，命中！求这一子句的结果表达式 -1 → -1
   （子句 2、子句 3 根本不会被看一眼）
5. cond 的值 = -1 → 过程体的值 = -1 → 调用返回 -1

另外两个用例同理：

三行输出 -1 / 0 / 1，与测试文件里写的完全一致。

Challenge：用 if 再写一遍

题目鼓励你两种都写。用嵌套 if 是这样（这段没进最终提交，是示意用的等价实现）：

(define (over-or-under-if num1 num2)
  (if (< num1 num2)
      -1
      (if (= num1 num2)
          0
          1)))

把它和 cond 版并排看，你会发现 cond 的第 k 条子句， 就是嵌套 if 的第 k 层的「真」分支；else 就是最内层那个「假」分支。 cond 不是新东西，它是把右倾的嵌套结构拍平成一列。

2. Compose（composed）

题目要什么

写一个过程 composed，它收两个过程 f 和 g， 返回一个新过程。这个新过程收一个数 x，返回「先对 x 用 g， 再把结果交给 f」的值，也就是数学上的 \(f \circ g\)。

官方测试 tests/composed.py 的 setup 里先准备了三个东西：

scm> (define (add-one a) (+ a 1))
scm> (define (multiply-by-two a) (* a 2))
scm> (define add-then-mul (composed multiply-by-two add-one))

然后跑这些用例：

scm> (add-then-mul 2)
6
scm> ((composed add-one add-one) 2)
4
scm> ((composed multiply-by-two multiply-by-two) 2)
8
scm> ((composed add-one multiply-by-two) 2)
5
scm> ((composed (composed add-one add-one) add-one) 2)
5
scm> ((composed (composed add-one add-one) multiply-by-two) 2)
6
scm> ((composed multiply-by-two (composed add-one add-one)) 2)
8

这几行值得逐个读一遍，因为它们精确地钉死了「谁先谁后」。看第四行： (composed add-one multiply-by-two) 作用在 2 上得 5。 如果顺序是「先 add-one 再 multiply-by-two」，结果会是 \((2+1)\times 2 = 6\)； 实际是 5，说明真实顺序是先 multiply-by-two（\(2 \times 2 = 4\)）再 add-one（\(4+1=5\)）。 composed 的第二个参数先跑。

再看 setup 里的 add-then-mul——名字叫「先加后乘」，定义是 (composed multiply-by-two add-one)，作用在 2 上得 \((2+1)\times 2 = 6\)， 和测试里写的 6 吻合。名字和参数顺序是反的，这正是 \(f \circ g\) 记法容易绊人的地方： 写在左边的后执行。

还有一处边界要注意：最后三行把 composed 的返回值又当成参数传给了 composed。这说明你返回的那个东西必须是「和 add-one 平起平坐的一等过程」， 而不是什么半成品。只要老老实实返回 lambda，这一点自动成立。

怎么想到的

这题在 Python 里你早就写过（Lab 3 / HW 2 的 compose1）：

def composed(f, g):
    def h(x):
        return f(g(x))
    return h

所以真正的问题只有一个：Scheme 里怎么「返回一个函数」？

代码

(define (composed f g)
  ; 返回一个新过程：先把 x 交给 g，再把结果交给 f
  (lambda (x) (f (g x))))

特别注意括号的数量：(f (g x)) 里有两对括号，各代表一次调用。 如果写成 (f g x)，意思就变成「把 g 和 x 两个参数一起传给 f」—— 而 add-one 只收一个参数，会报参数个数错误。

验证：手工追踪 (add-then-mul 2)

先看定义阶段发生了什么，再看调用阶段。

1. define 是特殊形式，先求最后那个子表达式：
   (composed multiply-by-two add-one)

2. 求算子 composed → 过程对象，形参 (f g)
3. 求算子数：
   multiply-by-two → 过程对象 P_mul
   add-one         → 过程对象 P_add
4. apply：新建帧 f1，parent = 全局
      f1: f = P_mul
          g = P_add
   在 f1 中求 (lambda (x) (f (g x)))
5. lambda 是特殊形式：不执行函数体，只造一个过程对象
   得到 λ1 = 过程(形参 x, 体 (f (g x)), parent = f1)
   ← 这一步是关键：λ1 记住了 f1，而 f1 里 f=P_mul、g=P_add
6. define 把 λ1 绑到全局帧的 add-then-mul，返回符号 add-then-mul

全局帧 (Global)
  add-one          → P_add   (形参 a, 体 (+ a 1))
  multiply-by-two  → P_mul   (形参 a, 体 (* a 2))
  composed         → P_comp  (形参 f g, 体 (lambda (x) (f (g x))))
  add-then-mul     → λ1

f1  [调用 composed 时建立]   parent: Global
  f → P_mul
  g → P_add
  返回值: λ1

λ1  形参: x
    体:  (f (g x))
    parent: f1        ← 闭包记住的环境

1. 求算子 add-then-mul → λ1
2. 求算子数 2 → 2
3. apply：新建帧 f2，parent = λ1 的 parent = f1
      f2: x = 2
   在 f2 中求 (f (g x))

4. 求 (f (g x))：
   a. 求算子 f：f2 里没有 f → 沿 parent 到 f1 → 找到 P_mul
   b. 求算子数 (g x)：
        求 g：f2 没有 → f1 里找到 P_add
        求 x：f2 里就有 → 2
        apply P_add：新建帧 f3，parent = Global，a = 2
                     体 (+ a 1) → 3
        (g x) = 3
   c. apply P_mul：新建帧 f4，parent = Global，a = 3
                   体 (* a 2) → 6

5. (f (g x)) = 6 → 返回 6

输出 6，与测试文件一致。注意第 4a 步：查 f 时走的是 λ1 的 parent 链（f2 → f1 → Global），而不是「调用点所在的环境」。 这就是词法作用域。如果 Scheme 用的是动态作用域，f 就会在调用者那里找， 这题根本没法工作。

验证：嵌套用例 ((composed multiply-by-two (composed add-one add-one)) 2)

外层是一个调用表达式，算子本身是个表达式，得先算出来：

1. 求算子 (composed multiply-by-two (composed add-one add-one))
   1.1 先求它自己的算子数（左到右）：
       multiply-by-two → P_mul
       (composed add-one add-one)
           → 建帧 fA: f = P_add, g = P_add
           → 返回 λA (体 (f (g x)), parent = fA)
   1.2 apply composed：建帧 fB: f = P_mul, g = λA
       返回 λB (体 (f (g x)), parent = fB)

2. 求算子数 2 → 2
3. apply λB：建帧 fC，parent = fB，x = 2
   求 (f (g x))：
     f 在 fB 里 = P_mul
     (g x)：g 在 fB 里 = λA，调用 λA(2)
            建帧 fD，parent = fA，x = 2
            求 (f (g x))：f 在 fA = P_add, g 在 fA = P_add
              (g x) = (add-one 2) = 3
              (f 3)  = (add-one 3) = 4
            λA(2) = 4
     (f 4) = (multiply-by-two 4) = 8

结果 8 ✓

算式写出来就是 \((2+1+1) \times 2 = 8\)，和测试里的 8 对上。 同一段代码，f 和 g 在不同的帧里指向不同的东西—— 这就是为什么闭包必须记住「创建时的帧」而不是「函数体的文本」。

3. Repeat（repeat）

题目要什么

写一个过程 repeat，收一个过程 f 和一个数 n， 返回一个新过程；这个新过程收 x，返回把 f 连续作用在 x 上 n 次的结果。

scm> (define (square x) (* x x))
square
scm> ((repeat square 2) 5) ; (square (square 5))
625
scm> ((repeat square 3) 3) ; (square (square (square 3)))
6561
scm> ((repeat square 1) 7) ; (square 7)
49

tests/repeat.py 里还有第二组用例：

scm> (define (increment x) (+ x 1))
increment
scm> ((repeat increment 4) 2) ; (increment (increment (increment (increment 2))))
6
scm> ((repeat increment 10) 51)
61

翻译成人话：(repeat f n) 就是 \(f^n\)（函数的 n 次自复合）。 题面给的注释已经把语义写死了：(repeat square 2) 等于 (lambda (x) (square (square x)))，不多不少。

边界情况：官方测试里 n 最小是 1。但你的实现几乎一定会碰到 n = 0—— 因为递归要有 base case。n = 0 意味着「一次都不作用」， 那新过程就该原样返回 x，也就是恒等函数（identity function）。 这个观察是整题的枢纽。

怎么想到的

题面给了提示：上一题的 composed 可能有用。顺着这条线走。

代码

(define (repeat f n)
  ; 重复 0 次就是恒等函数；否则先做一次 f，再把剩下 n-1 次接在外面
  (if (= n 0)
      (lambda (x) x)
      (composed f (repeat f (- n 1)))))

验证：手工追踪 ((repeat square 2) 5)

(repeat square 2)
  n = 2，(= n 0) → #f，走假分支
  需要求 (composed f (repeat f (- n 1)))
  先算算子数：f → P_sq；(repeat square 1)

      (repeat square 1)
        n = 1，(= n 0) → #f
        先算算子数：f → P_sq；(repeat square 0)

            (repeat square 0)
              n = 0，(= n 0) → #t
              返回 (lambda (x) x) → 记作 ID
              ★ 到底了，开始回代

        (composed P_sq ID) → 建帧 g1: f = P_sq, g = ID
                          → 返回 λ1，parent = g1

  (composed P_sq λ1) → 建帧 g2: f = P_sq, g = λ1
                    → 返回 λ2，parent = g2

(repeat square 2) 的值 = λ2

此时内存里是这样一条链：

λ2  形参 x，体 (f (g x))，parent = g2
        g2: f = P_sq(square)   g = λ1

λ1  形参 x，体 (f (g x))，parent = g1
        g1: f = P_sq(square)   g = ID

ID  形参 x，体 x，parent = Global

1. apply λ2 于 5：建帧 h1，parent = g2，x = 5
   求 (f (g x))：
     f → 沿 h1→g2 找到 P_sq
     (g x)：g → g2 里是 λ1，参数 x = 5，调用 λ1(5)

     2. apply λ1 于 5：建帧 h2，parent = g1，x = 5
        求 (f (g x))：
          f → g1 里是 P_sq
          (g x)：g → g1 里是 ID，调用 ID(5)

          3. apply ID 于 5：建帧 h3，x = 5，体 x → 5
             ID(5) = 5

          (f 5) = (square 5) = 25
        λ1(5) = 25

     (f 25) = (square 25) = 625
   λ2(5) = 625

输出 625，等于 (square (square 5))，与测试注释一致。 可以看到 square 恰好被调用了 2 次，中间那次 ID 什么也没做—— 它只是让递归有个干净的底。

再验一个：((repeat increment 4) 2)

得 6，与测试一致。((repeat increment 10) 51) 同理是 \(51 + 10 = 61\)。 用 increment 来验证比用 square 好，因为加法不满足「顺序无所谓」的巧合掩盖， 数字直接告诉你 f 被作用了几次。

4. WWSD: Lists（wwsd_lists）

题目要什么

WWSD = What Would Scheme Display，「Scheme 会显示什么」。 用 python3 ok -q wwsd_lists -u 解锁，一共九问，全都围绕 cons / list / 引号（quote）三者的区别。这些题不写代码， 但它们是理解后面 Q5、Q6 的前提：你必须能一眼看出一个表达式造出来的是什么形状的数据。

先把三条规则摆清楚，后面逐问对照：

另外要分清「一个列表」和「它打印出来的样子」。 Scheme 打印列表时省略掉所有 cons 和 nil：一串 pair \(p_1 \to p_2 \to \cdots \to \text{nil}\) 打印成 (元素1 元素2 ...)。 所以看到输出 (1 2)，你要能反推出内部是两个 pair 串成的链。

逐问讲

1) (cons 1 (cons 2 nil)) → (1 2)

scm> (cons 1 (cons 2 nil))
(1 2)

从里往外算。(cons 2 nil) 造一个 pair：car = 2，cdr = 空表。 这是个合法列表，打印成 (2)。再 (cons 1 那个)：car = 1，cdr = (2)。 链子是 1 → 2 → nil，打印成 (1 2)。

盒指针（box-and-pointer）：

 +---+---+     +---+---+
 | 1 | ------>| 2 | / |
 +---+---+     +---+---+

 / 表示 nil（空表），打印时不出现

这和 Python 里 Link(1, Link(2, Link.empty)) 是同一个东西。

2) (car (cons 1 (cons 2 nil))) → 1

car 取 pair 的第一格。上面那条链的第一格是 1，所以答案是 1， 不是 (1)。car 返回的是元素本身，不是只含它的列表。 对应 Python 的 link.first。

3) (cdr (cons 1 (cons 2 nil))) → (2)

cdr 取第二格，也就是那条 2 → nil 的子链。 它是个列表，所以打印成 (2) 而不是 2。 第 2、3 问放在一起就是要你看清 car 和 cdr 的返回类型不同： 一个是元素，一个是列表。这条区分在 Q6 写递归时会救你的命。

4) (list 1 2 3) → (1 2 3)

list 是普通过程，参数照常求值（1 2 3 求值成自己）， 然后把它们串成一个长度为 3 的链。等价于 (cons 1 (cons 2 (cons 3 nil)))， 写起来省心得多。

5) '(1 2 3) → (1 2 3)

引号版。'(1 2 3) 是 (quote (1 2 3)) 的简写： 不求值，直接把括号里那段结构当数据造出来。因为里面全是数字字面量， 求值与不求值结果一样，所以这一问和第 4 问输出相同——但机制完全不同。 下一问就会把差别暴露出来。

6) (cons 1 '(list 2 3)) → (1 list 2 3)

scm> (cons 1 '(list 2 3))  ; Recall quoting
(1 list 2 3)

1. cons 是普通过程，两个参数都要求值。
2. 求第一个参数 1 → 1
3. 求第二个参数 '(list 2 3)：
   quote 是特殊形式，不求值里面的东西。
   于是得到一个三元素列表，元素依次是：
     符号 list（不是那个内建过程，就是个 symbol）
     数字 2
     数字 3
   这个列表打印出来是 (list 2 3)
4. cons 1 到它前面 → 四元素列表：1, list, 2, 3
5. 打印 (1 list 2 3)

如果这里写的是 (cons 1 (list 2 3))（没有引号）， 那第二个参数会被调用，得到列表 (2 3)，最终结果是 (1 2 3)。 一个引号，差别就这么大。

7) (cons 1 `(list 2 3)) → (1 list 2 3)

这里用的是反引号（quasiquote，准引号），题面注释直说了 「Quasiquotes also work as quotes」。在没有 unquote（逗号）的情况下， 反引号的行为和普通引号完全一样：整段都不求值。所以答案和第 6 问一模一样。 出这一问是为了让你看到反引号并不神秘——只有当里面出现 ,expr 时它才会「开个口子」 去求值那一小段，本次作业不涉及。

8) '(cons 4 (cons (cons 6 8) ())) → (cons 4 (cons (cons 6 8) ()))

scm> '(cons 4 (cons (cons 6 8) ()))
(cons 4 (cons (cons 6 8) ()))

整个表达式被引号罩住，一个字都不求值，所以输出就是原文照抄。 这一问是全套里最容易慌的一问——你会本能地去算里面的 cons， 甚至注意到 (cons 6 8) 若真求值会报错（cdr 不是列表也不是 nil， 正如题面所说 (cons 1 2) 会 Error）。但引号意味着它永远不会被求值， 所以不会报错，它只是一段静静躺着的数据。

那这段数据到底是什么形状？它是一个三元素列表：

注意末尾的 ()：它是空列表，作为最内层列表的第三个元素出现， 打印时也就原样打印成 ()。它跟「链的末端那个不打印的 nil」不是一回事—— 这里的 () 是一个元素，所以看得见。

9) (cons 1 (list (cons 3 nil) 4 5)) → (1 (3) 4 5)

没有引号，所有东西都要求值，从里往外：

1. (cons 3 nil) → 单元素列表，打印为 (3)
2. (list (那个) 4 5) → 三元素列表：
     元素0 = 列表 (3)      ← 元素本身是个列表！
     元素1 = 4
     元素2 = 5
   打印为 ((3) 4 5)
3. (cons 1 上面这个) → 四元素列表：1, (3), 4, 5
   打印为 (1 (3) 4 5)

 +---+---+   +---+---+   +---+---+   +---+---+
 | 1 | ---->| * | ---->| 4 | ---->| 5 | / |
 +---+---+   +-|-+---+   +---+---+   +---+---+
               |
               v
             +---+---+
             | 3 | / |
             +---+---+

关键在于分清「把元素接到链上」和「把整个列表当成一个元素」。 cons 的第一个参数总是变成一个元素——哪怕它自己是个列表。 所以 (3) 在结果里是嵌套的一层括号，而不是被摊平成 1 3 4 5。 想摊平得用 append。

验证

这九问在 tests/wwsd_lists.py 里是明文存着的（'locked': False）， 答案就是上面写的那些。跑 python3 ok -q wwsd_lists 时， ok 会真的把每一行喂给 Scheme 解释器，拿实际输出和文件里的期望值比对， 所以这些答案不是「据说」，是解释器亲口说的。

5. Make a List（lst）

题目要什么

题面给了一张盒指针图（box-and-pointer diagram），要你定义一个名字 lst 指向那个结构。 题面里的图我们看不到原图文件，但解锁测试把答案钉死了—— tests/make_structure.py 里第二个用例写着：

scm> lst ; type out exactly how Scheme would print the list that will be defined in this problem (see spec)
((1) 2 (3 4) 5)

所以目标非常明确：造一个四元素的列表，依次是

它长这样：

lst
 |
 v
+---+---+   +---+---+   +---+---+   +---+---+
| * | ---->| 2 | ---->| * | ---->| 5 | / |
+-|-+---+   +---+---+   +-|-+---+   +---+---+
  |                       |
  v                       v
+---+---+               +---+---+   +---+---+
| 1 | / |               | 3 | ---->| 4 | / |
+---+---+               +---+---+   +---+---+

主链有四个 pair（因为顶层有四个元素）；第一个和第三个 pair 的 car 指向另一条链， 而不是一个数。「元素本身是列表」正是 Q4 第 9 问练的那件事。

怎么想到的

这题的难点不在语法，在读图。给一张盒指针图写出构造代码， 核心是先回答两个问题，顺序不能反。

代码

(define lst
  ; 对应盒指针图：第一个元素是子列表 (1)，第三个元素是子列表 (3 4)
  (list (list 1) 2 (list 3 4) 5))

Challenge：换几种方式造同一个结构

题面鼓励用不同构造器写出同一个列表。下面几种都会打印成 ((1) 2 (3 4) 5) （这几段是示意，最终提交的是上面那版）：

; 全部用 cons 手搭
(cons (cons 1 nil)
      (cons 2
            (cons (cons 3 (cons 4 nil))
                  (cons 5 nil))))

; 整体用引号一次写完
'((1) 2 (3 4) 5)

; 混合：外层 list，子表用引号
(list '(1) 2 '(3 4) 5)

三者造出的结构完全相同。list 版最好读；引号版最短，但要记住引号里的东西 不会求值——如果某个元素需要算（比如 (+ 1 1)），引号版就不能用了。

验证

解锁测试的第一个用例是一段热身，把它手工走一遍，正好复习 car/cdr 的嵌套：

scm> (define a '(1))
a
scm> a
(1)
scm> (define b (cons 2 a))
b
scm> b
(2 1)
scm> (define c (list 3 b))
c
scm> c
(3 (2 1))
scm> (car c)
3
scm> (cdr c)
((2 1))
scm> (car (car (cdr c)))
2
scm> (cdr (car (cdr c)))
(1)

a = (1)                 一个 pair: car=1, cdr=nil
b = (cons 2 a)          新 pair: car=2, cdr=a  → 打印 (2 1)
                        注意 a 没有被复制，b 的 cdr 就是 a 那个 pair
c = (list 3 b)          两个元素的列表: 元素0=3, 元素1=b
                        → 打印 (3 (2 1))，b 整体成为一个元素

(car c)                 主链第一个 pair 的 car = 3
(cdr c)                 主链剩下部分 = 只含一个元素 b 的列表
                        该元素是 (2 1)，所以打印 ((2 1))  ← 两层括号
(car (cdr c))           取出那个唯一元素 → b，即 (2 1)
(car (car (cdr c)))     b 的 car → 2
(cdr (car (cdr c)))     b 的 cdr → a，即 (1)

最容易错的是 (cdr c) 那一问：答案是 ((2 1)) 而不是 (2 1)。 因为 c 有两个元素，去掉第一个之后剩下的是一个含单个元素的列表， 外面那层括号是「列表」的括号，里面那层是「元素恰好也是列表」的括号。 这里也顺带看到别名（aliasing）：b 的 cdr 和 a 是同一个 pair， (cdr (car (cdr c))) 拿到的就是 a 本身。

然后是本题自己的验证。测试 setup 先跑 (load-all ".") 把 lab09.scm 加载进来， 于是 lst 已被定义。再求值 lst：

求 (list (list 1) 2 (list 3 4) 5)：

1. list 是普通过程，四个算子数从左到右求值：
   (list 1)   → 链 [1|nil]           打印 (1)
   2          → 2
   (list 3 4) → 链 [3|·]→[4|nil]     打印 (3 4)
   5          → 5
2. apply list：把这四个值串成四个 pair 的主链
3. 打印：遍历主链，逐个打印元素，元素是列表就再加一层括号
   → ((1) 2 (3 4) 5)  ✓

6. Without Duplicates（without-duplicates）

题目要什么

实现 without-duplicates：收一个数字列表 lst，返回一个新列表， 包含 lst 中所有不重复的元素，且按它们第一次出现的顺序排列。 例如 (without-duplicates (list 5 4 5 4 2 2)) 得 (5 4 2)。

tests/without_duplicates.py 的全部用例：

scm> (without-duplicates (list 5 4 2))
(5 4 2)
scm> (without-duplicates (list 5 4 5 4 2 2))
(5 4 2)
scm> (without-duplicates (list 5 5 5 5 5))
(5)
scm> (without-duplicates ())
()
scm> (without-duplicates '(5 4 3 2 1))
(5 4 3 2 1)
scm> (without-duplicates '(5 4 3 2 1 1))
(5 4 3 2 1)
scm> (without-duplicates '(5 5 4 3 2 1))
(5 4 3 2 1)
scm> (without-duplicates '(12))
(12)
scm> (without-duplicates '(1 1 1 1 1 1))
(1)

把这些用例读出信息量：

第三条最关键：(5 4 5 4 2 2) 里的重复是隔开的， 所以「只比较相邻两个」的做法（那是 uniq，不是去重）会失败。 第五条排除了「先排序再去相邻重复」的偷懒法——排序会把 (5 4 3 2 1) 变成 (1 2 3 4 5)。

怎么想到的

先说一条错误的路，因为大多数人都会先想到它。

代码

(define (without-duplicates lst)
  (if (null? lst)
      nil
      ; 保留表头，再把余下部分中所有与表头相等的元素滤掉后继续递归
      (cons (car lst)
            (without-duplicates
              (filter (lambda (x) (not (= x (car lst))))
                      (cdr lst))))))

验证：手工追踪 (without-duplicates (list 5 4 5 4 2 2))

第 0 层  lst = (5 4 5 4 2 2)
  (null? lst) → #f
  (car lst) = 5
  (cdr lst) = (4 5 4 2 2)
  filter 保留 ≠5 的：      (4 4 2 2)
  → 结果 = (cons 5 (without-duplicates (4 4 2 2)))

第 1 层  lst = (4 4 2 2)
  (car lst) = 4
  (cdr lst) = (4 2 2)
  filter 保留 ≠4 的：      (2 2)
  → 结果 = (cons 4 (without-duplicates (2 2)))

第 2 层  lst = (2 2)
  (car lst) = 2
  (cdr lst) = (2)
  filter 保留 ≠2 的：      ()
  → 结果 = (cons 2 (without-duplicates ()))

第 3 层  lst = ()
  (null? lst) → #t
  → 返回 nil          ★ 触底

第 3 层 返回 nil                  打印 ()
第 2 层 (cons 2 nil)      = (2)
第 1 层 (cons 4 (2))      = (4 2)
第 0 层 (cons 5 (4 2))    = (5 4 2)   ✓

输出 (5 4 2)，与测试一致。注意第 0 层那次 filter： 它一口气把位置 2 上的那个 5 也删掉了，虽然它跟头并不相邻。 这就是为什么这个解法能处理「隔开的重复」，而只比较相邻元素的写法不能。

再看两个边界用例

第三行值得多看一眼：全同元素的表只递归两层就结束了， 因为一次 filter 就把所有重复清空。而如果用「逐个比对 seen 集合」的写法， 这里得走满六层。这个解法在重复很多时反而更快。

复杂度

设列表长 \(n\)、去重后有 \(k\) 个不同元素。递归深度是 \(k\)（每层消掉一个不同的值）， 每层的 filter 要扫一遍当前剩余的表，代价 \(O(n)\)。 所以总代价是 \(\Theta(nk)\)，最坏（全不相同）是 \(\Theta(n^2)\)。 这和 Python 里用 set 的 \(\Theta(n)\) 比是慢的， 但在没有哈希表的纯函数式设定下，\(\Theta(n^2)\) 是很正常的代价， 本题也没有性能要求。

不用 filter 的写法（对照）

如果不用 filter，也可以走「判断头是否在尾巴里出现过」的思路， 但那需要一个额外的 contains? 辅助过程，而且顺序会变： 如果你写「若头在尾巴里还会出现，就丢掉头」，那 (5 4 5 4 2 2) 保留的是 最后 一次出现的位置，得到 (5 4 2) 恰好也对，但 (1 2 1) 会得到 (2 1) 而不是 (1 2)。题目要的是首次出现的顺序， 所以这条路必须小心。filter 版天然正确，这也是提示推荐它的原因。

7. 整份作业回顾

如果只让你从这份 lab 里带走一句话：语法是表皮，求值规则是骨头。 你换到一门括号语言，写法全变了，但「先算算子、再从左到右算算子数、再 apply」 这条规则、以及「函数记住自己被创建时的环境」这条规则，一个字都没变。

三条可迁移的思维方法

自测