4

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

我们想要的是一个简洁的解决方案，使用调用来反转 Scheme 中的列表，以及使用foldl调用的不同解决方案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方案可能需要更多思考。

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

4

2 回答 2

2

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

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

这种foldr情况只是稍微难一些，只要记住foldr处理列表中的元素的顺序与它们在输入列表中出现的顺序相同。同样，您必须找到正确的调用程序：

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

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

于 2013-11-05T01:42:34.337 回答
1

您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)
于 2013-11-05T22:31:06.077 回答