如何反转一个列表？

Question

在Scheme中，反转列表的函数是什么？

它需要能够处理嵌套列表。因此，如果您执行类似于(reverse '(a (b c d) e))这样的操作，则输出应为(e (b c d) a)。

我该如何解决这个问题？我不仅仅是在寻找答案，而是想要学习一些东西。

- 安杰帅

---

更好的答案：（define（rev1 lst）（foldl cons'() lst）） - wowest

通常情况下，当我看到“_它需要能够处理嵌套列表_”时，那意味着(reverse '(a (b c d) e))应该得到 (e (d c b) a)，即嵌套的列表也被反转。但是对于(reverse '(a (b c (d e))))，你期望得到什么？我会期望得到 (((e d) c b) a) ，但例子表明结果应该是 ((b c (d e)) a)。 - ad absurdum

Answer 1

(define (my-reverse ls)
  (define (my-reverse-2 ls acc)
    (if (null? ls)
      acc
      (my-reverse-2 (cdr ls) (cons (car ls) acc))))
  (my-reverse-2 ls '()))

这里使用一个累加器变量来翻转列表，从传入的列表中取出第一个元素，将其连接到累加器的前面。它隐藏了累加器函数，并且只公开接受列表作为参数的函数，所以调用者不必传入空列表。这就是为什么我有我的my-reverse-2函数。

(my-reverse-2 '(a (b c d) e) '()); will call
(my-reverse-2 '((b c d) e)  '(a)); which will call
(my-reverse-2 '(e)  '((b c d) a)); which will call
(my-reverse-2 '() '(e (b c d) a)); which will return
'(e (b c d) a)

因为my-reverse-2函数中的最后一个函数调用是对my-reverse-2的调用，并且返回值被直接传递（第一次调用的返回值就是第二次调用的返回值，以此类推），my-reverse-2是尾递归优化的，这意味着它不会在堆栈上耗尽空间。因此，使用任意长度的列表调用它是安全的。

如果要应用于嵌套列表，请使用以下方式：

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc))
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

在将元素添加到列表之前，此代码会检查它是否为列表，并在是列表时先将其翻转。 由于它调用自身来反转内部列表，因此可以处理任意嵌套。

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)，尽管有一个嵌套的列表，但结果仍按照反字母顺序排列。 它的计算过程如下：

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

- Theo Belaire

Answer 2

使用：

(define (reverse1 l)
  (if (null? l)
     nil
     (append (reverse1 (cdr l)) (list (car l)))
  )
)

解释：

规则：

1. 如果列表为空，则翻转后的列表也为空
2. 否则，在翻转的列表尾部添加列表的第一个元素

这段代码可以这样理解：

reverse1 是函数名，l 是参数。如果列表为空，则返回空。 否则，调用 reverse1 函数并将 (cdr l)（即列表的尾部）附加到第一个元素 (car l) 组成的列表中。

在你的示例中（伪代码）：

1st iteration
l=>(a (bcd)e)
car l => a
cdr l => (bcd)e
list(car l) =>(a)
------------------
reverse( cdr l)"+"(a)
------------------
2nd iteration
l=>((bcd)e)
car l => (bcd)
cdr l =>e
list(car l)=>(bcd)
--------------------
reverse(cdr l)"+"((bcd))+(a)
-----------------------
3rd iteration
l=>e
car l=> e
cdr l => nil
list (car l) =>(e)
-------------------------
(e (bcd)a)

- trix

---

请注意，这个答案是用Common Lisp编写的，它使用nil代替'()。 - erjiang

@erjiang，那并不完全正确——虽然 Common Lisp 使用 nil 而 Scheme 不用，但是在这个答案的顶部定义的函数实际上是 Scheme 而不是 Common Lisp。不过你需要执行类似于 (define nil '()) 这样的操作才能使它起作用。 - okonomichiyaki

这段代码对我来说完美地运行，只需要进行一个小修改（返回项而不是nil）： (define (rev items) (if (null? items) items (append (rev (cdr items)) (list (car items))) ) ) 我在Petite Chez（http://www.scheme.com/）中运行此代码。 - Puterdo Borato

还有一个内置的（反向）过程，返回相同的结果。 - Puterdo Borato

为了避免空列表的问题，因为你已经知道 l 是空的，从 (null? l) 中，那种情况可以直接返回 l。这将适用于无论 null? 检查什么。 - Joshua Taylor

请注意，此实现可能存在性能问题。请查看以下链接以查看更好的列表反转实现版本：http://www.cs.sfu.ca/CourseCentral/310/pwfong/Lisp/2/tutorial2.html - Hugo Barauna

Answer 3

这是一个在Racket中的反转函数，我比Scheme更喜欢它。它仅使用匹配模式匹配函数。

(define/match (rev l)
    [('()) '()]
    [((list a ... b)) (cons b (rev a))])

> (rev '(a (b c d) e))
'(e (b c d) a)

- fp_mora

---

这个算法的时间复杂度为O(n^2)，空间复杂度也是O(n^2)。因此，随着列表变得越来越长，你很可能在耐心耗尽或内存用尽之前无法得到答案。为了使内容更加通俗易懂，可以翻译为：这种算法需要花费O(n^2)的时间和O(n^2)的空间。因此，当列表变得越来越长时，你很可能在等待回答之前失去耐心或者内存不足。 - Sylwester

Answer 4

这是一种适用于嵌套列表的反转函数的方法：

(define (reverse-deep l)
  (map (lambda (x) (if (list? x) (reverse-deep x) x)) (reverse l)))

伪代码解释:
首先按照通常的方式反转列表
然后对于反转列表中的每个元素:
- 如果该元素本身就是一个列表: 递归应用此过程
- 否则: 不要改变该元素

- Anton Holmberg

Answer 5

您可以使用foldr简单地反转列表中的元素：

(foldr (lambda (a r) (append r (list a))) empty lst)

- E 4 6

Answer 6

我使用了类似于插入排序的代码：

(define deep-rev-list
  (lambda (l)
     (cond ((null? l) (quote ()))
           ((atom? (car l))
             (swap-till-end (carl) (deep-rev-list (cdr l))))
           (else
             (swap-till-end (deep-rev-list (car l)) (deep-rev-list (cdr l)))))))


(define swap-till-end
   (lambda (elm lst)
      (cond ((null? lst) (cons elm '()))
            (else
               (cons (car lst) (swap-till-end elm (cdr lst)))))))

(define atom?
  (lambda (x)
    (and (not (null? x)) (not (pair? x)))))

我是凭记忆重现的。可能会有一些错误。如果有的话，我会更正代码。但使用的技术类似于《小计算机程序员》中嵌套列表的命令ments :). 我在DrRacket中进行了检查。

(deep-rev-list '((1 2) (3) ((4 5)))) 返回 (((5 4)) (3) (2 1))

- Rajesh Bhat

---

"The Little Schemer" 和 "DrRacket" 是什么？分别是一本书和一个在线工具吗？ - Peter Mortensen

Answer 7

我的解决方案：

(define (rvrs ls)
  (if (null? ls)
    empty
    (append (rvrs (cdr ls)) (cons (car ls) empty))))

- fabior

---

需要进行解释。例如，这个想法是什么？它与以前的答案有何不同之处？ - Peter Mortensen