我提出了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，我看到球拍支持一级延续。我想知道使用shift和reset来表达foldr的第二次实现是否可能/有益。我玩了一会儿，结果我的脑子里外翻了个底朝天。
请给出充分的解释。
免责声明:
-
你试图解决的
foldr的"问题"实际上是它的主要特点。 - 从根本上说，你不能简单地反向处理一个列表，你能做的最好的事情就是先反转它。λ您的解决方案,在其本质上,从递归没有什么不同,只是不是积累递归调用栈上的你是显式地积累它们在许多λ,所以唯一的收获是,而不是栈大小的限制,你可以多少记忆深刻,因为λ,可能的是,在堆上分配的,权衡是你现在执行动态内存分配/回收为每个"递归调用"。
现在，让我们来看看实际的答案。
让我们试着实现foldr，记住我们可以使用延续。这是我的第一次尝试:
(define (foldr3 f y xs)
(if (empty? xs)
y
(reset
(f (car xs) (shift k (k (foldr3 f y (cdr xs))))))))
; ^ Set a marker here.
; ^ Ok, so we want to call `f`.
; ^ But we don’t have a value to pass as the second argument yet.
; Let’s just pause the computation, wrap it into `k` to use later...
; And then resume it with the result of computing the fold over the tail.
如果你仔细观察这段代码，你会发现，它和你的foldr完全一样——即使我们"暂停"计算，我们也会立即恢复计算，并将递归调用的结果传递给它，当然，这个结构不是尾部递归的。
好，那么看起来我们需要确保我们不立即恢复它，而是先执行递归计算，然后用递归计算结果恢复暂停的计算。让我们重新编写函数，让它接受continuation，并在实际计算出所需的值后调用它。
(define (foldr4 f y xs)
(define (aux k xs)
(if (empty? xs)
(k y)
(reset
(k (f (car xs) (shift k2 (aux k2 (cdr xs))))))))
(reset (shift k (aux k xs))))
这里的逻辑与之前的版本类似:在if的非平凡分支中，我们设置了一个reset标记，然后开始计算表达式，就好像我们已经拥有了所需的一切;然而，在现实中，我们还没有列表尾部的结果，所以我们暂停计算，将它"打包"到k2中，并执行一个递归调用(这次是尾部)，说"嘿，当你得到结果时，继续这个暂停的计算"。
如果你分析这段代码是如何执行的，你会发现其中绝对没有什么神奇之处，它只是在遍历列表时将延续一个接一个地"包装"起来，然后，一旦它到达末尾，延续就被"打开包装"，并以相反的顺序一个接一个地执行。事实上，这个函数和foldr2做的完全一样——区别仅仅是语法上的:reset/shift模式不是创建显式的lambdas，而是允许我们立即开始写出表达式，然后在某个时候说"稍等一下，我还没有这个值，让我们暂停一下，稍后返回"……但在引擎盖下，它最终创建了与lambda相同的闭包!
我相信，没有比这更好的方法了。
另一个免责声明:我没有一个工作的Scheme/Racket解释器与reset/shift实现，所以我没有测试函数