43

我一直在与The Little Schemer一起学习 Scheme 并在我的环境中使用 PLT-Scheme。

Little Schemer在递归方面为我提供了极大的帮助（现在对我来说很简单），但我被困在书中介绍“收集器”并将函数作为一个整体称为延续的部分。

这是他们使用的示例代码。我理解递归元素，但我被困住了，特别是在 lambda 函数上——我的头脑无法遵循路径以及该 lambda 函数的参数是如何设置的（因为它们唯一的调用是在递归中再次调用它们，所以有在函数体内没有具体使用）。

如果有人可以通过将函数递归到 lambda 收集器中或多或少地给我分解计算路径，那可能会对我有所帮助。

;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
  (cond
    ((null? l)
      (col (quote ()) 1 0))
    ((atom? (car l))
      (cond
        ((even? (car l))
          (even-only-collector (cdr l)
            (lambda (newl p s)
              (col (cons (car l) newl)
                (* (car l) p) s))))
         (else
           (even-only-collector (cdr l)
             (lambda (newl p s)
               (col newl
                 p (+ (car l) s)))))))
    (else
      (even-only-collector (car l)
        (lambda (al ap as)
          (even-only-collector (cdr l)
            (lambda (dl dp ds)
              (col (cons al dl)
                (* ap dp)
                (+ as ds)))))))))

;; The collector function
(define (collector newl product sum)
  (cons sum
    (cons product newl)))

先感谢您！！

4

2 回答 2

43

尝试一些更简单的东西来看看它是如何工作的。例如，这是一个list-sum接收延续参数（通常称为k）的函数版本：

(define (list-sum l k)
  (if (null? l)
    ???
    (list-sum (cdr l) ???)))

基本模式就在那里，而缺少的部分就是有趣的事情发生的地方。continuation 参数是一个期望接收结果的函数——所以如果列表为空，很明显我们应该发送它0，因为这是总和：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) ???)))

现在，当列表不为空时，我们使用列表的尾部递归调用函数（换句话说，这是一个迭代），但问题是延续应该是什么。这样做：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) k)))

显然是错误的——这意味着k最终将收到总和(cdr l)而不是全部l。相反，在那里使用一个新函数，它将把ltoo 的第一个元素与它接收的值相加：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))

这越来越近了，但仍然是错误的。但是最好考虑一下事情是如何工作的——我们调用list-sum一个延续，它本身将接收总和，并将我们现在看到的第一个项目添加到其中。缺失的部分在我们忽略k. 我们需要的是用这个函数组合 k——所以我们做同样的求和运算，然后将结果发送到k：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))

这终于奏效了。（顺便说一句，请记住，这些lambda函数中的每一个都有自己的“副本” l。）你可以试试这个：

(list-sum '(1 2 3 4) (lambda (x) x))

最后请注意，这与以下内容相同：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))

如果你明确组合。

（您也可以在中级 + lambda 学生语言中使用此代码，然后单击步进按钮以查看评估如何进行 - 这将需要一段时间才能完成，但您将看到延续函数如何嵌套，每个拥有自己的列表视图。）

于 2010-01-07T04:32:34.307 回答
1

这是帮助您“获得更具体的想法”的一种方法。想象一下，如果收集器是这样定义的：

(define (collector l p s)
  (display l)
  (newline)
  (display p)
  (newline)
  (display s)
  (newline))

您可以在基本情况下看到，如果您传入一个空列表，它将使用参数'()、1 和 0 调用您的函数。现在，使用单元素列表，看看它将使用什么来调用您的函数。继续处理越来越长的列表，直到你弄清楚发生了什么。

祝你好运！

于 2010-01-07T03:27:27.777 回答