使用foldl和foldr反转Scheme中的列表

Question

如何使用foldr和foldl定义一个函数来反转Scheme中的列表？

我们想要的是一个简洁的解决方案，使用foldl调用和使用foldr调用来反转Scheme中的列表，定义如下：

(define (foldl operation lst initial)
    (if (null? lst) initial
        (foldl operation 
               (cdr lst) 
               (operation (car lst) initial))))

和

(define (foldr operation lst initial)
    (if (null? lst) initial
        (operation 
            (car lst) 
            (foldr operation (cdr lst) initial))))

精明的人会注意到foldl实现是尾部递归的，因为返回的值是在调用每个递归步骤时计算的——在最后一步，整个答案已经计算完毕，并简单地返回到链上。

foldr实现不是尾部递归的，因为它必须使用向上传递回递归链的值来构建返回值。

因此，我们感兴趣的两个Scheme实现应该采用以下形式，

(define (rev1 lst)
    (foldl ___________________________
**Solution:**
(define (rev1 lst)
    (foldl cons lst '()))

和

(define (rev2 lst)
    (foldr ___________________________
**Solution 1:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (foldr cons accumulator (cons element '())))
       lst '())) 
**Solution 2:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (append accumulator (cons element '())))
       lst '())) 

最终目标是能够调用以下

(rev1 '(1 2 3)) -> (3 2 1)
(rev2 '(1 2 3)) -> (3 2 1)

foldl解决方案应该是相对琐碎的(基于我们的直觉(，但foldr解决方案可能需要更多的思考。

以前与此问题类似(但记录较少(的问题最终没有得到回答和/或关闭

Answer 1

这看起来像是家庭作业，所以我会给你一些提示，让你开始。foldl的情况很琐碎，你只需要找到要传递的正确函数，并记住：foldl可以被可视化为向后处理列表(最后一个元素在前，第一个元素在后(，所以你所要做的就是将列表中的当前元素与累积值粘在一起：

(define (rev1 lst)
  (foldl <???> lst '()))

foldr的情况只是稍微困难一些，只需记住foldr以与输入列表中出现的元素相同的顺序处理列表中的元素。同样，你必须找到正确的调用程序：

(define (rev2 lst)
  (foldr (lambda (e a)
           <???>)
         lst
         '()))

您需要以某种方式将e(当前元素(放在a的端，即累积值。提示：您会发现append和list在这里很有用。

Answer 2

您的rev1"解决方案"未编译。。。如果你用l 代替list

> (define (rev1 l) 
    (foldl cons l '()))
> (rev1 '(1 2 3))
(3 2 1)

对于您的rev2，它作为主体工作：

> (foldr (lambda (a b) (append b (list a))) '(1 2 3) '())
(3 2 1)