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

Question

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

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

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.

对于a,map您需要创建一个过程,cons该过程将所提供的过程应用于具有累加器的元素.这就是fold-right最终需要获取列表的内容.您当前的解决方案没有,cons所以您将无法获得列表.

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

由于我认为这是家庭作业,我会让你做实际的实施.快乐的黑客.