了解 Racket 中的移位/重置

Question

foldr我在球拍中展示了两个简单的实现

第一个缺乏适当的尾部调用，对于较大的值来说是有问题的xs

(define (foldr1 f y xs)
  (if (empty? xs)
      y
      (f (car xs) (foldr1 f y (cdr xs)))))

(foldr1 list 0 '(1 2 3))
; => (1 (2 (3 0))

第二个使用带有延续的辅助函数来实现正确的尾部调用，使其可以安全地用于较大的值xs

(define (foldr2 f y xs)
  (define (aux k xs)
    (if (empty? xs)
        (k y)
        (aux (lambda (rest) (k (f (car xs) rest))) (cdr xs))))
  (aux identity xs))

(foldr2 list 0 '(1 2 3))
; => (1 (2 (3 0)))

看看racket/control我发现球拍支持一流的延续。foldr我想知道使用shiftand表达第二种实现是否可能/有益reset。我把玩了一会儿，结果我的大脑彻底翻了个底朝天。

请对任何答案提供详尽的解释。我在这里寻求大局观的理解。

Answer 1

免责声明：

\n

\n
1. foldr您试图解决的 \xe2\x80\x9cproblem\xe2\x80\x9d实际上是它的主要功能。
\n
2. 从根本上来说，你不能轻易地反向处理列表，你能做的最好的就是先反向处理它。使用 lambda 的解决方案本质上与递归没有什么不同，它只是在堆栈上累积递归调用，而不是在许多 lambda 中显式累积它们，因此唯一的好处是由于受到堆栈大小的限制，您可以使用尽可能多的内存，因为 lambda 很可能是在堆上分配的，而权衡是您现在为每个 \xe2\x80 执行动态内存分配/解除分配\x9c递归调用\xe2\x80\x9d。
\n

\n

现在，抛开这个问题，我们来看看实际的答案。

\n\n

让\xe2\x80\x99s 尝试实现，foldr记住我们可以使用延续。这是我的第一次尝试：

\n

(define (foldr3 f y xs)\n  (if (empty? xs)\n    y\n    (reset \n      (f (car xs) (shift k (k (foldr3 f y (cdr xs))))))))\n  ; ^ Set a marker here.\n  ;    ^ Ok, so we want to call `f`.\n  ;               ^ But we don\xe2\x80\x99t have a value to pass as the second argument yet.\n  ;                 Let\xe2\x80\x99s just pause the computation, wrap it into `k` to use later...\n  ;                 And then resume it with the result of computing the fold over the tail.\n

\n

如果你仔细观察这段代码，你会发现，它与你的 \xe2\x80\x93 完全相同，foldr即使我们 \xe2\x80\x9cpause\xe2\x80\x9d 计算，然后我们立即恢复它并将递归调用的结果传递给它，当然，这种构造不是尾递归的。

\n

好吧，那么看来我们需要确保我们不是立即恢复它，而是先执行递归计算，然后用递归计算结果恢复暂停的计算。让\xe2\x80\x99s 重新设计我们的函数以接受延续，并在实际计算出所需的值后调用它。

\n

(define (foldr4 f y xs)\n  (define (aux k xs)\n    (if (empty? xs)\n      (k y)\n      (reset\n        (k (f (car xs) (shift k2 (aux k2 (cdr xs))))))))\n  (reset (shift k (aux k xs))))\n

\n

这里的逻辑与之前的版本类似：在 的非平凡分支中，我们if设置一个reset标记，然后开始计算表达式，就好像我们已经拥有了所需的一切一样；然而，实际上，我们还没有列表尾部的结果，因此我们暂停计算，将 \xe2\x80\x9c 将其 \xe2\x80\x9d 打包为k2，并执行（这次是尾部）递归调用\xe2\x80\x9chey，当你\xe2\x80\x99得到结果时，恢复这个暂停的计算\xe2\x80\x9d。

\n

如果你分析这段代码是如何执行的，你\xe2\x80\x99会发现它绝对没有魔法，它的工作原理只是\xe2\x80\x9cwrapping\xe2\x80\x9d在遍历列表，然后，一旦到达末尾，延续就是 \xe2\x80\x9cunwrapped\xe2\x80\x9d 并以相反的顺序一一执行。事实上，这个函数的作用与foldr2\xe2\x80\x93 的作用完全相同，区别只是语法上的：reset/shift模式允许我们立即开始写出表达式，然后在某个时刻说 \，而不是创建显式 lambda。 xe2\x80\x9chold 稍等一下，我还不\xe2\x80\x99t 有这个值，让\xe2\x80\x99s 在这里暂停并稍后返回\xe2\x80\x9d...但在引擎盖下它最终结束创建相同的闭包lambda！

\n

我相信，没有比这更好的列表方法了。

\n

另一个免责声明：我没有\xe2\x80\x99t有一个工作的Scheme/Racket解释器，并且实现了reset/ shift，所以我没有\xe2\x80\x99t测试这些功能。

\n