使用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解决方案可能需要更多的思考。 之前类似于这个问题的问题（但文档少得多）最终没有得到答案或被关闭。

- Jason Parham

---

@JoshuaTaylor 你得到的是一个列表，但不同之处在于元素的顺序不同。这与OP对foldl/foldr的定义相同，只是初始值是最后一个参数。 - Sylwester

我觉得你做得很好。 - Sylwester

@Sylwester Oy; 我当时发帖太晚了，可能有点糊涂。我不确定我在想什么。我将删除评论，建议在这里使用此答案没有用处。 - Joshua Taylor

Answer 1

这似乎是作业，我会给你一些提示以帮助你开始。在foldl的情况下，很容易，你只需要发现正确的函数传递，并记住：foldl可以被视为向后处理列表（最后一个元素先处理，第一个元素最后处理），所以你所要做的就是将列表中的当前元素与累加值粘合在一起：

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

foldr的情况稍微复杂一点，只需记住foldr按照输入列表中元素出现的顺序处理列表中的元素即可。同样地，您必须找到正确的过程进行调用：

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

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

- Óscar López

---

你正在使用 SRFI-1 的 folds，而不是由 OP 提供的其中 lst 和 initial-value 被交换的那个。 - Sylwester

Answer 2

您的rev1“解决方案”无法编译……如果您将list替换为l，它将会编译成功。

> (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)

- GoZoner