理解Scheme中的fold-left和fold-right

Question

我的任务是使用fold-left或fold-right在Scheme中实现'map'函数和'filter'函数的最基本版本。我很难理解这些函数到底在做什么。以下是我的代码：

(define (myMap f l)
    (fold-left (lambda (f a) (f a)) '() l))

(define (myFilter f l)
    (fold-left f '() l))

下面的代码是我直觉上认为应该这样写的。对列表l中的每个元素应用一个过滤器（比如数字），并将结果放到空列表中。顶部的代码完全错误，但我感觉它更接近正确的方向。可以使用一种lambda函数来将该函数应用于一个数字。

以下是所需输出的示例：

(myMap sqrt '(4 9 16 25)) ; (2 3 4 5)
(myFilter odd? '(1 2 3 4 5)) ; (1 3 5)

- amza

---

这里的诀窍是，与map和filter不同，fold不一定返回一个列表。折叠操作比map和filter更通用（正如可以通过fold来定义它们所证明的那样）。例如，使用它将列表（“reduce”是fold的常见替代名称）减少到总和可能更容易理解折叠的作用。尝试(fold-left + 0 '(1 2 3 4 5))，看看我的意思。 - Alexis King

@AlexisKing 这是我在很多文档中找到的示例。我知道它像(... (+ (+ (+ 0 1) 2) 3) ...)这样应用，但我如何扩展它以执行任意函数？我猜想类似(lambda (f l n) (append (f n) l))这样的东西，这样我就可以将我应用函数的元素添加回列表中？或者这样做没有意义？ - amza

不，问题在于提供给fold的过程的元素不是列表。您无法在非列表上调用append。为了使fold返回一个列表，您的累加器函数必须在每个累加步骤中显式执行构建新列表的职责。这就是折叠的含义：它是一种封装了遍历列表并将每个值复合到“累加器”值上的功能操作。累加函数接收当前累加器和新值，并生成一个新的累加器。 - Alexis King

@amza 不是的，这里是类似(... (+ 3 (+ 2 (+ 1 0))) ...)，针对左折叠而言。并非所有的 + 都是可交换的（a+b == b+a但a-b != b-a）。 - Will Ness

虽然与您的问题并不直接相关，但我曾经深入地写过关于左折叠和右折叠的内容：http://codereview.stackexchange.com/a/87626/216。它甚至包括了一些非常类似于 map 和 filter 的实现。 - C. K. Young

Answer 1

fold-left 和 fold-right 都使用一个归约过程从第一个元素到最后一个元素减少一个或多个列表，但是应用的顺序在 fold-right 中保持不变，而在 fold-left 中则被反转。如果您执行以下操作，则很容易显示：

#!r6rs
(import (rnrs))

;; helper for R6RS fold-left since argument order is swapped
(define (xcons d a) 
  (cons a d))

(fold-left xcons '() '(1 2 3 4)) ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

我制作 xcons 的原因是对于 left-fold，累加器是第一个参数。在 SRFI-1 列表库 中，fold-left 相当于只被称为 fold，并且与 fold-right 具有相同的参数顺序：

(import (rnrs base)
        (only (srfi :1) fold fold-left))

(fold cons '() '(1 2 3 4))       ; ==> (4 3 2 1)
(fold-right cons '() '(1 2 3 4)) ; ==> (1 2 3 4)

一个左折叠是尾递归的，因为它处理第一个元素并成为下一次迭代的累加器。右折叠需要在连接到倒数第二个元素之前将最后一个元素连接到累加器上。这意味着如果可能的话应该避免使用右折叠，并且在许多情况下（例如查找最大元素）使用左折叠是可以的。

在 map 和 filter 的情况下，您希望结果按照相同的顺序排列，因此必须始终使用 fold-right。

对于映射，您需要创建一个过程，该过程将应用提供的过程的结果与累加器结合起来。这就是 fold-right 需要最终得到列表的原因。您当前的解决方案中没有 cons，因此您将不会得到列表。

对于筛选，您需要创建一个过程，如果谓词的结果是 true 值，则将原始元素连接到累加器上，否则仅评估累加器。

由于我认为这是作业，所以我会让你自己实现。祝你编程愉快！

- Sylwester

Answer 2

考虑一个fold函数的含义：它接受一个两个参数的函数（我们称之为“迭代器”）和一个列表，并重复地将迭代器应用到列表的元素上，方式是在通用步骤中，使用列表的当前元素和迭代器先前应用的结果来调用该函数（在第一步中，先前的结果只是fold的第三个参数）。

因此，例如，fold-right从列表的末尾开始，并在每个“步骤”中以这种方式应用迭代器。

(iterator current-element previous-result) ;; produces: next result

为了产生结果以作为下一个应用程序的右参数，需要使用“feed”方法。类似于fold-left，不同之处在于该函数从列表头部开始应用，并将前一个结果用作左参数。

因此，如果您要按照这种方式定义map，请考虑必须构建一个“迭代器”函数，该函数必须按照上述方式应用。也就是说，该函数必须将f应用于当前元素，并生成下一次迭代中使用的结果。由于我们想要构建此应用程序结果列表，因此迭代器的主体可以简单地为：

(cons (f current-element) previous-result)

整个函数变成了：

(define (myMap f lst)
  (define (iterator current-element previous-result)
    (cons (f current-element) previous-result))
  (fold-rigth iterator '() lst))

既然这是一个练习，我将让您来定义myFilter：这一次，您必须找到一个适当的迭代器体，使得只有在将函数应用于当前元素返回true时，当前元素才会被“插入”到结果中，否则它必须被忽略。

另一个有趣的练习是使用fold-left来实现这两个函数。由于迭代器应用的不同顺序，这两个函数略微更加复杂。

- Renzo

Answer 3

折叠函数表达了一种递归的预设模式。左折叠遍历列表中的所有元素，从左到右，使用一个将当前元素和当前累加器组合以产生下一个累加器值的函数来转换累加器，这个累加器值将在下一次调用组合函数时使用，例如：

(fold-left <+> [a,b,c..,n] z) === (n <+> (... <+> (c <+> (b <+> (a <+> z)))...))

因此，

(define (myMap-lt f lst)
  (fold-left 
    (lambda (elem     ; list's element
             accum    ; accumulator so far
             )
         ( ... (f elem)    ; map applies f on each elem
              ... accum    ; accum holds list-of-results-so-far
                   ... )   ; need to extend it with this elem's result
       ) 
    '()               ; initial value of the accumulator
    lst))

右折叠类似，但它将当前元素与从右侧递归处理的结果组合在一起。

(fold-right <+> [a,b,c..,n] z) === (a <+> (b <+> (c <+> (... <+> (n <+> z)...))))

在这两种情况下，合并函数实际上是相同的，即将cons操作和f函数本身进行函数组合。但其中一个会产生反向的结果（哪个？）。您可以通过调用reverse的后处理步骤来解决这个问题。

- Will Ness