recursion - 解释 The Little Schemer 第 137 页上的延续示例

Question

有问题的代码是这样的:

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen))))))

我整天盯着这个，但我似乎不太明白。当您再次使用该函数时，您正在重新定义 col但在示例中，他们似乎使用了原始定义。为什么不改。你怎么能在不传入参数的情况下重复它 newlat和 seen .

很难解释我的问题，因为我似乎只是遗漏了一部分。如果也许有人可以给出比这本书更明确的演练，我也许能够理解它是如何工作的。

Answer 1

让我们看一个例子；也许这会有所帮助。 :-) 为简单起见，我将使用 list作为收集器/延续，它只会返回一个带有延续参数的列表。

(multirember&co 'foo '(foo bar) list)

在开始时，

a = 'foo
lat = '(foo bar)
col = list

在第一次迭代中， (eq? (car lat) a)条件匹配，因为 lat不为空，且 lat的第一个元素是 'foo .这将设置下一个递归到 multirember&co因此:

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

在下一次迭代中， else匹配:自 lat不为空，且 lat的第一个元素是 'bar (而不是 'foo )。因此，对于下一次递归，我们有:

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

为了便于人类阅读(并避免混淆)，我们可以重命名参数(由于词法范围)，而无需更改程序的语义:

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

最后， (null? lat)子句匹配，因为 lat现在是空的。所以我们叫

(col '() '())

扩展为:

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

其中(当替换 newlat1 = '() 和 seen1 = '() 时)变成

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

或(正在评估 (cons 'bar '()))

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

现在，替换值 newlat2 = '(bar)和 seen2 = '() ，我们得到

(list '(bar) (cons 'foo '()))

或者，换句话说，

(list '(bar) '(foo))

给出我们的最终结果

'((bar) (foo))