解释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匹配:since 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))

Answer 2

multirember&co很长一段时间以来，我一直在努力理解内部发生的事情。问题是，当我以为我已经得到它的那一刻 - 下一个任务/示例证明我还没有。

对我有帮助的是整合正在发生的事情的视觉表示（对我来说，文本演练很难理解，出于某种原因）。

因此，我整理了两个流程图：

其一，仅显示递归不同步骤之间的关系：

另一种反映实际值：



现在，每当我感觉自己又失去了“争论的线索”时，我只要参考这个流程图，它就会让我回到正轨。

通过流程图查看“全貌”后我了解到的另一件事是，该a-friend函数只是检查是否seen包含任何值（尽管它以相反的方式返回它，即#f当有值时seen和#t何时seen为空，这可能会令人困惑。

PS：我为 做了类似的流程图evens-only*&co，它出现在本书后面。

Answer 3

我在这里找到了一个很好的答案:http: //www.michaelharrison.ws/weblog/？p = 34

我也一直在努力解决这个问题.关键是要理解词汇范围(对我来说,javascript)和内部函数传递给eq上的multirember&co而不是eq分支.了解这一点,您将了解整个过程.

Answer 4

上面的链接（http://www.michaelharrison.ws/weblog/?p=34）很好地解释了整个练习是如何避免命令式编程（C，Java）需要声明两个“持有者”或“收集器” “变量（或列表、向量）显式地存在于内存中，以便在您迭代列表时捕获您的答案。通过 FP 语言方案使用延续，您在单步执行（草莓金枪鱼和剑鱼）时不会将测试结果“推送”到任何单独创建的“篮子”中；相反，当您发送适当的 consing 函数时，您将两个列表组合在一起 - 一个用于 eq? 是的，另一个为 eq？false——通过重复。。。最后结束于第三个 col 函数，在 TLS 的第一个示例中，它是“a-friend”，它询问为保存所有匹配而构建的列表是否为空（null？）。然后，TLS 要求您使用新的“最后”列再次“运行”multirember&co，该列仅询问包含所有“非金枪鱼”原子的列表包含多少个原子（“最后的朋友”）。因此，有两个“一流”函数用于处理收集任务，即构建两个单独的列表，然后在递归展开结束时，原始 col（“朋友”）提出最终问题。也许“multirember&co”这个名字并不是最伟大的名字，因为它实际上不会重建列表减去要删除的原子；相反，它构建两个单独的列表（永远不会显示），然后应用最终的 col (a-friend 或 last-friend) 。。。它显示#t 或#f，或“非金枪鱼”列表的长度。

这是一些输出：

> (multirember&co 'tuna '(and tuna) a-friend)
#f
> (multirember&co 'tuna '(and not) a-friend)
#t

这是一个返回不匹配列表的 col：

(define list-not  (lambda (x y) x))

及其用途：

> (multirember&co 'tuna '(and not) list-not)
(and not)