functional-programming - 了解 Racket 中的移位/重置

Question

我介绍了 foldr 的两个简单实现在 Racket 中

第一个缺少适当的尾调用并且对于 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我看到 Racket 支持一流的延续。我想知道表达 foldr 的第二个实现是否可能/有益使用 shift和 reset .我玩了一会儿，我的大脑最终翻了个底朝天。

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

Answer 1

免责声明:

foldr的“问题”您试图解决的实际上是它的主要功能。

从根本上说，您不能轻松地反向处理列表，您能做的最好的事情就是先将其反向。您使用 lambda 的解决方案本质上与递归没有什么不同，只是不是在堆栈上累积递归调用，而是在许多 lambda 表达式中显式地累积它们，因此唯一的好处是不受堆栈的限制大小，您可以使用尽可能多的内存，因为 lambda 很可能在堆上分配，权衡是您现在为每个“递归调用”执行动态内存分配/释放。

现在，让我们来看看实际的答案。

让我们尝试实现 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 完全相同。 – 即使我们“暂停”了计算，我们也会立即恢复它并将递归调用的结果传递给它，当然，这种构造不是尾递归的。
好的，那么看来我们需要确保我们不会立即恢复它，而是先执行递归计算，然后使用递归计算结果恢复暂停的计算。让我们重新设计我们的函数以接受一个延续并在它实际计算出它需要的值后调用它。

(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做的完全一样确实 - 区别仅仅是语法上的:而不是创建显式 lambda，reset/shift模式允许我们立即开始写出表达式，然后在某个时候说“等一下，我还没有这个值，让我们在这里暂停，稍后返回”......但在幕后它最终创建与 lambda 相同的闭包将!
我相信，使用列表没有比这更好的方法了。
另一个免责声明:我没有 reset 的工作方案/ Racket 解释器/shift实现了，所以我没有测试功能。