学习计划，尝试推行地图

Question

我试图实现地图使用与折叠在计划。我引用了这个站点：ref1，这是我从第一个元素中理解折叠、=>左关联折叠(foldl)折叠/迭代的方式。(向前)右关联折叠(foldr)折叠/从最后一个元素迭代。(向后) Q1，我明白了吗？

来自ref1 : foldl，foldr的实现

 `1) foldl (left-associate fold)`
  (define (foldl func accum lst)
   (if (null? lst)
        accum
        (foldl func (func accum (car lst)) (cdr lst))))

2) foldr (right-associate fold)
 (define (foldr func end lst)
   (if (null? lst)
      end
      (func (car lst) (foldr func end (cdr lst)))))

=>用折叠实现映射，ref1也有带折叠代码的映射，就是这样。

1) map implementation using foldr from ref1.
  (define (map func lst)      
     (foldr (lambda (x y) (cons (func x) y)) '() lst))

**[Q2] map impelementation using foldl from myself** 
  (define (fold-map-left pr list)
    (foldl 
       (lambda (sublist element) (cons (pr element) sublist))
       '() 
       list)
  what I get as the output...
  e.g. (fold-map-left (lambda(n) (expt n n)) '(1 2 3 4)) 
       output => (256 27 4 1): backwards 

• 我知道左关联折叠/向后迭代，所以首先要把最后一个折叠放到输出中.那么我能做什么使输出按正确的顺序进行呢？我的代码还有什么问题吗？

Answer 1

首先，我认为您的foldl实现有点不正确，在Scheme中实现它的通常方法是(但是一定要阅读@JoshuaTaylor的评论以了解结果)：

(define (foldl func accum lst)
  (if (null? lst)
      accum
      (foldl func
             (func (car lst) accum) ; here's the change
             (cdr lst))))

关于第一个问题:这两种折叠都从左到右使用输入列表，但它们在构建输出结果的方式上有所不同：foldl在开始时累加第一个输入元素，然后在结果的基础上累加第二个元素，依此类推；如果我们构建一个列表作为输出，那么第一个元素将是最后一个(并用这个示例测试您自己的foldl实现，以了解为什么我说它有点错)：

(foldl cons '() '(1 2 3 4 5))
=> '(5 4 3 2 1)

另一方面，foldr递归地前进，直到到达空列表，然后，当递归开始展开时，最后一个元素首先被累积，然后在结果的顶部积累第二到最后的元素，等等，这样就保持了输入的相同顺序：

(foldr cons '() '(1 2 3 4 5))
=> '(1 2 3 4 5)

关于第二个问题:根据map实现foldr会更简单，因为正如我们之前看到的那样，它保留了输入顺序。这与您的相同，但具有更好的格式和变量名称：

(define (map func lst)
  (foldr (lambda (ele acc)
           (cons (func ele) acc))
         '()
         lst))

但是，当然，我们可以使用foldl并在结束时反转结果(或者:在将列表传递给foldl之前反转列表)：

(define (map func lst)
  (reverse
   (foldl (lambda (ele acc)
            (cons (func ele) acc))
          '()
          lst)))

同时拥有foldl和foldr的想法是什么？这是一种权衡(请务必阅读@ChrisJester的评论，从性能的角度讨论实现方面的问题)。在构建输出时，foldr将保持与输入相同的顺序，但它将生成一个与输入大小成正比的递归过程:注意，func是在调用递归调用后执行的。

另一方面，foldl将以反向顺序构建输出，但它将生成一个在常量空间中运行的迭代过程:注意，在调用递归调用之后没有什么可做的了，因此它的尾递归和Scheme被优化以有效地处理这种递归。