《The Seasoned Schemer》第一章scramble函数工作机制解析

核心规则 #

scramble函数接收一个非空元组，元组内任意元素的值不大于其自身对应的1基索引，返回与输入长度相同的元组。输入中的每个数值都是从自身位置向元组前端回溯的反向索引，每个位置的输出，就是从当前位置按该索引向前数到的对应位置的数值。

实现拆解 #

整个实现分三个函数，逻辑非常精简，核心巧思是用累积参数存逆序前缀，避免每次回溯都从头遍历原列表。

1. 基础取值函数pick #

(define pick
  (λ (i lat)
    (cond
      ((eq? i 1) (car lat))
      (else (pick (sub1 i)
                  (cdr lat))))))

pick是Scheme里很常见的1基索引取值函数：传入索引i和列表lat，i为1时直接取列表首元素，否则把i减1、去掉列表首元素递归调用，直到定位到目标元素。

2. 核心迭代函数scramble-b #

(define scramble-b
  (lambda (tup rev-pre)
    (cond
      ((null? tup) '())
      (else
       (cons (pick (car tup) (cons (car tup) rev-pre))
             (scramble-b (cdr tup)
                         (cons (car tup) rev-pre)))))))

这是实际完成计算的内部函数，两个参数分别是待处理的剩余元组tup，以及已经处理过的前缀元素组成的逆序列表rev-pre：

• 终止条件：待处理元组为空时返回空列表，递归结束。
• 处理当前元素时，先把当前首元素(car tup)拼到rev-pre头部，得到的新列表刚好是「从当前元素开始，往原列表头部方向排列的所有元素」——新列表第1位是当前元素，第2位是原列表中当前元素的前一个元素，第k位就是从当前位置向前数k个的元素，刚好和反向索引的计数规则完全匹配。
• 直接用当前元素的值当索引，调用pick从上面拼好的列表里取值，就是当前位置的输出值。
• 递归处理剩余元组时，把当前元素加入逆序前缀列表，作为下一层递归的累积参数。

3. 外层包装函数scramble #

(define scramble
  (lambda (tup)
    (scramble-b tup '())))

外层函数只做初始化，传入原始元组，把逆序前缀的初始值设为空列表，启动递归即可。

示例验证 #

拿第二个示例(scramble '(1 2 3 4 5 6 7 8 9))举例：

• 处理第1个元素1：拼完的逆序列表是(1)，pick 1得到1，累积前缀更新为(1)
• 处理第2个元素2：拼完的逆序列表是(2 1)，pick 2得到1，累积前缀更新为(2 1)
• 处理第3个元素3：拼完的逆序列表是(3 2 1)，pick 3得到1，累积前缀更新为(3 2 1)
• 后续每个位置n的元素值都是n，拼完的逆序列表长度刚好为n，pick n取到的永远是列表最后一位的1，所以最终输出全1，和示例结果完全一致。
  其余示例按照同样的步骤推导，都能和给出的返回值匹配。

内容的提问来源于stack exchange，提问作者Hermann