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

Question

所以我的任务是在 Scheme 中使用 fold-left 或 fold-right 实现最基本版本的 '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-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如果谓词的结果是真值，则将原始元素添加到累加器，如果不是，则仅评估累加器。

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