了解 Scheme 中的左折和右折

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))

最下面的是我凭直觉认为应该是的。应用过滤器（比如 number? 到 l 的每个元素并将结果放入空列表）。顶部是完全错误的，但我觉得它更像是在正确的轨道上。使用某种 lambda 函数将函数应用于数字？

这是我正在寻找的输出示例：

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

Answer 1

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

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

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

产生的结果将作为正确的参数“提供”给下一个应用程序。与 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 的定义留给你：这次你必须找到一个合适的迭代器主体，以便将当前元素“插入”到结果中仅当应用于它的函数 returns 为真时，否则必须忽略它。

另一个有趣的练习是对这两个函数使用fold-left。考虑到迭代器的不同应用顺序，函数稍微复杂一些。

Answer 2

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

(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 函数本身。但是其中之一会产生结果 reversed（哪个？）。您可以通过调用 reverse.

的 post 处理步骤来解决此问题

Answer 3

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 List library 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.

对于 map 您需要创建一个过程，该过程 cons 将提供的过程应用于具有累加器的元素的结果。这就是 fold-right 最终得到列表所需要的。您当前的解决方案没有任何 cons，因此您不会获得列表。

对于 filter，如果谓词的结果为真值，则需要创建一个过程，将 cons 原始元素添加到累加器，如果不是，则只计算累加器.

因为我认为这是家庭作业，所以我会让你去做实际的实施。快乐黑客。

了解 Scheme 中的左折和右折

Understanding fold-left and fold-right in Scheme

scheme

functional-programming

fold