functional-programming - 了解 Scheme 中的 fold-left 和 fold-right

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

(define (myMap f l)
    (fold-left (lamda (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)

最佳答案

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)

左折叠是尾递归的，因为它处理第一个元素并成为下一次迭代的累加器。右折叠需要先将最后一个元素 cons 到累加器，然后再将倒数第二个元素一直到第一个。这意味着应该尽可能避免右折叠，并且在许多情况下，如果结果的顺序或您折叠为单个值(例如，找到最大元素)左折叠是可以的。

在 map 和 filter 的情况下，您希望结果的顺序相同，因此您需要始终使用 fold-right 。

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

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

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

关于functional-programming - 了解 Scheme 中的 fold-left 和 fold-right，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32686736/