代码之家 › 专栏 › 技术社区 › Ixmatus

帮助理解方案中的延续

the-little-schemer continuations racket lisp scheme

43

Ixmatus · 技术社区 · 16 年前

我一直在一起工作 小阴谋家 在我的环境中学习和使用PLT方案。

小阴谋家 在递归方面帮了我很大的忙(现在对我来说很简单),但我还是坚持在书中介绍“collectors”并将函数作为一个整体调用为一个延续。

下面是他们使用的示例代码。我了解递归元素,但是我被卡住了,尤其是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)))

提前谢谢!你说什么?

2 回复 | 直到 11 年前

1

42

Eli Barzilay 16 年前

尝试一些更简单的方法来看看这是如何工作的。例如,这里有一个版本的 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 .相反,在这里使用一个新函数,它将总结 L 以及它收到的值:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) 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学生语言中使用此代码,然后单击“步进器”按钮查看评估的进展情况--这将需要一段时间才能完成,但您将看到如何嵌套延续函数,每个函数都有自己的列表视图。)

2

1

C. K. Young 16 年前

这里有一种方法可以帮助你“得到一个更具体的想法”。想象一下,如果收集器是这样定义的:

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

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

祝你好运!