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

Question

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

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

(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在这里很有用。