MIT Scheme中的fold过程是什么方向？

Question

如果我想在 MIT Scheme 中反转一个列表，我可以用 (fold cons '() list) 来实现，这样如果列表是 (define lis '(1 2 3 4))，那么 (fold cons '() lis) 给出 (4 3 2 1)。有两种折叠，左折叠和右折叠，但如果我使用 (fold-right cons '() lis)，我会得到 (1 2 3 4)，所以普通折叠不可能是那种。另外，如果我使用 (fold-left cons '() lis)，我会得到 ((((() . 1) . 2) . 3) . 4)，所以这也不能成为原始示例中的折叠。反转列表需要什么样的折叠？

我问是因为我希望能够做出这样的通用折叠：

(define ls '((1 2 3) (4 5 6)))
(gen-fold cons '() ls)
=> ((6 5 4) (3 2 1))
(define l2 '(((1 2) (2 3)) ((3 4) (4 5))))
(gen-fold cons '() ls)
=> (((5 4) (4 3)) ((3 2) (2 1)))

编辑：为了更好地提出问题，这些图表描述了我认为在调用 '(fold cons '() '(1 2 3)) 时发生的列表轮换，假设 fold 是修改后的 fold-left 根据亚历克西斯国王：

(define lis (list '(1 2 3))

     cons
    /   \
   1    cons
        /  \
       2   cons
           /  \
          3   '()

(cons lis '())

         cons
        /  \
      cons '()
     /  \
    1   cons
       /   \
      2    cons
           /  \
          3   '()

(fold-left (cons lis '()))

        cons
       /    \
    cons     cons
   /  \      /  \
  2   cons  1   '()
      /  \
     3   '()


        cons
       /    \
    cons     cons
   /  \       /  \
  3   '()    2    cons
                  /   \
                1     '()

   cons
  /  \
 3   cons
     /  \
    2   cons
        /  \
       1   '()

Answer 1

MIT Scheme 在其基础库中不包含 fold 函数，只有 SRFI-1 声明的 fold-left and fold-right. However, there does exist a fold 函数，它受 MIT Scheme 支持并表现出您描述的行为。

fold函数是左折叠——也就是说，它通过从左到右的迭代来累积列表——但它与MIT Scheme的fold-left函数的不同之处在于参数顺序累加器过程被翻转。也就是说，fold 应用累加器参数 last 提供的过程，而 fold-left 应用累加器参数 first[=63] 的过程=].

为了说明这一点，可以这样定义 fold fold-left:

(define (fold proc init lst) (fold-left (lambda (x acc) (proc acc x)) init lst))

根据我的经验，fold 参数顺序在 Lisp 实现中更常见，而 fold-left 参数顺序在其他函数式语言中更常见。提供 acc 参数 last 的原因正是您发现的原因：它使 fold 与 cons 一起使用更容易-就像接受累加值作为第二个参数的过程。

顺便说一句，您似乎在最初的问题中混淆了 fold-left 和 fold-right： returns 列表不变 fold-right 而 fold-left 即 returns 对的倒置集合。如果您了解 fold-left 和 fold-right 的定义方式，这就很有意义了。

以某种方式，fold-left 和 fold-right 都从 left 开始折叠列表，因为 Scheme 列表是单链接的并且不能从右边读。区别在于左折叠是迭代的，右折叠是递归的。

左折叠对每个元素一个一个地应用程序，然后将结果穿入下一个应用程序。当被视为嵌套应用程序时，这最终会颠倒元素的顺序：

(proc eN ... (proc e1 (proc e0 init)) ...)

相比之下，右折叠递归地应用程序，在嵌套应用程序中保持顺序一致：

(proc e0 (proc e1 ... (proc eN init) ...))

与cons一起使用时，左折反转，右折只是标识。

（这在像 Haskell 这样的惰性语言中可能更有趣，因为右折叠并不依赖于整个列表，尽管据称是“从右边开始的”，所以它可以在无限流上运行......但是，这在 Scheme 中的相关性要小得多。）

MIT Scheme中的fold过程是什么方向？

What direction is the fold procedure in MIT Scheme?

scheme

reduce

fold

mit-scheme