使用foldl和foldr反转Scheme中的列表 [英] Reverse a list in Scheme with foldl and foldr

问题描述

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

How can you define a function to reverse a list in Scheme by using foldr and foldl?

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

What we want is a succinct solution to reverse a list in Scheme using a foldl call and a different solution using a foldr call, as defined:

(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实现是尾递归的，因为返回值是在调用每个递归步骤时计算出来的-在最后一步，整个答案已经计算出来，并简单地沿链返回.

The astute person will observe that the foldl implementation is tail-recursive because the returned value is computed as each recursive step is called - at the last step the entire answer is already computed and simply returned up the chain.

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

The foldr implementation is not tail-recursive because it must build the returned value by using the values that are passed back up the recursive chain.

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

Therefore, the two Scheme implementations that we are interested in should be in the following form,

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

最终目标是能够调用以下内容，

The end goal is to be able to call the following,

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

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

The foldl solution should be relatively trivial (based on our intuition), but the foldr solution will probably require some more thought.

与该问题类似的先前问题(但文献记载少得多)最终没有答案和/或结束.

推荐答案

这看起来像是家庭作业，因此，我将为您提供一些入门提示. foldl情况很简单，您只需要发现要传递的正确函数，并记住:foldl可以可视化为向后处理列表(最后一个元素在前，最后一个元素在后)，因此您要做的就是将列表中的当前元素与累积值结合在一起:

This looks like homework, so I'll give you some hints to get you started. The foldl case is trivial, you just have to discover the right function to pass, and remember: foldl can be visualised as processing the list backwards (last element first, first element last), so all you have to do is stick together the current element in the list with the accumulated value:

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

foldr的情况只是稍微难一点，请记住，foldr以与输入列表中出现的顺序相同的顺序处理列表中的元素.同样，您必须找到正确的程序才能调用:

The foldr case is only slightly harder, just remember that foldr processes the elements in the list in the same order as they appear in the input list. Again, you have to discover the correct procedures to call:

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

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

You need to somehow put e (the current element) at the end of a, the accumulated value. Hint: you'll find that append and list are useful here.

这篇关于使用foldl和foldr反转Scheme中的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！