如何只使用基本操作来递归反转一个列表？

Question

我想知道如何仅使用基本操作，如cons、first、rest、empty？等来反转列表。

不允许使用辅助函数或累加器，并且该函数仅接受一个输入 - 一个列表。

有人告诉我这是可能的，尽管我无法理解它。

到目前为止，这就是我构思的内容。 我不知道如何形成其余列表的递归。

(defunc rev-list (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (rev-list (rest x)))
            ???)))

显然，使用一个交换列表第一个和最后一个元素的函数也是可能的，尽管我也没有完全理解它。以下是其代码：

(define swap-ends (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (swap-ends (rest x))) 
            (swap-ends (cons (first x) 
                             (rest (swap-ends (rest x))))))))

- b33k3rz

---

这里的car和cdr的概念可能会对你有所帮助。 - JDong

我知道如何使用first（car）和rest（cdr），但我不明白如何为列表的递归构建正确的列表。 - b33k3rz

Answer 1

（注：答案在本文底部）第二个函数，

(define (swap-ends x)                                   ; swap [] = []
  (if (or (equal (length x) 0) (equal (length x) 1))    ; swap [x] = [x]
      x                                                 ; swap (x:xs) 
      (cons (first (swap-ends (rest x)))                ;    | (a:b) <- swap xs 
            (swap-ends (cons (first x)                  ;    = a : swap (x : b)
                             (rest (swap-ends (rest x))))))))

“你问它是做什么的？”，if语句的替代子句数据流图如下：

                   /-> first ----------------------> cons
x --> first ------/-------------> cons --> swap --/
  \-> rest -> swap ---> rest ---/

（从左到右按箭头方向）。因此，

[] -> []
[1] -> [1]
                     /-> 2 -----------------------> [2,1]
[1,2] --> 1 --------/------------> [1] --> [1] --/
      \-> [2] -> [2] ---> [] ---/

                           /-> 3 -------------------------> [3,2,1]
[1,2,3] --> 1 ------------/----------> [1,2] --> [2,1] --/
        \-> [2,3] -> [3,2] -> [2] --/

                             /-----> 4 ----------------------------> [4,2,3,1]
[1,2,3,4] --> 1 ------------/---------------> [1,3,2] -> [2,3,1] -/
          \-> [2,3,4] -> [4,3,2] -> [3,2] -/

到目前为止，它确实交换了列表的末尾元素。让我们通过自然归纳来证明它， < p > < em > < strong > < code > true（N-1）=> true（N） ：

                       /-> N --------------------------------------> [N,2..N-1,1]
[1..N] --> 1 ---------/-----------> [1,3..N-1,2] -> [2,3..N-1,1] -/
       \-> [2..N] -> [N,3..N-1,2]   /
                    -> [3..N-1,2] -/

所以它被证明了。因此，我们需要设计一个数据流图，在假设反转一个（N-1）长度的列表的情况下，可以反转一个N长度的列表：

[1..N] --> 1 ------------------------------------\
       \-> [2..N] -> [N,N-1..2] -> N -------------\------------------\
                     \-> [N-1,N-2..2] -> [2..N-1] -> [1..N-1] -> rev -> cons

这给我们提供了实现。

(define (rev ls)                                 ; rev [] = []
  (cond                                          ; rev [x] = [x]
    ((null? ls) ls)                              ; rev (x:xs) 
    ((null? (rest ls)) ls)                       ;   | (a:b) <- rev xs 
    (else                                        ;   = a : rev (x : rev b)
      (cons (first (rev (rest ls)))
            (rev (cons (first ls)
                       (rev (rest (rev (rest ls))))))))))

(rev '(1 2 3 4 5))     ; testing
;Value 13: (5 4 3 2 1)

在评论中的Haskell翻译非常自然地遵循了图表。它实际上是可读的: a 是最后一个元素，b 是反转的“核心”(即输入列表除去第一个和最后一个元素)，所以我们反转了反转的核心，加上第一个元素得到输入列表的butlast部分，然后将其反转并添加最后一个元素。简单明了。 :) 2020更新: 这里有一个基于代码的Scheme版本，由@Rörd从评论中提供，使其同样易读，使用参数解构代替Haskell的模式匹配。

(define (bind lst fun)
  (apply fun lst))

(define (rev lst)
  (if (or (null? lst)
          (null? (cdr lst)))
    lst
    (bind lst
      (lambda (first . rest)
         (bind (rev rest)
           (lambda (last . revd-core)
              (cons last (rev (cons first (rev revd-core))))))))))

- Will Ness

---

这里尝试使Scheme版本同样易读：https://gist.github.com/roerd/7117783。 - Rörd

Answer 2

(define (reverse x)
  (let loop ((x x) (y '()))
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))))

这确实是少数高效的方法之一，但仍然是一种辅助程序。

还有另外一种方式，但不是尾递归的，如果append不使用set-cdr！对于大型列表来说真的无法使用。

(define (reverse L)
  (if (null? l)
      '()
       (append (reverse (cdr L)) (list (car L)))))

- WorBlux

---

在之前（现已删除的）答案中，OP表示他也不能使用append。你的第一个变体使用了一个辅助函数，就像我的第二个变体一样。我认为严格遵守OP的所有限制是不可能的，很可能他误解了问题描述。 - Óscar López

Answer 3

你的环境中是否有last和butlast？如果是，那么可以像这样定义该过程（尽管正如Oscar所指出的那样，这并不是你通常想要解决问题的方式）：

(define (rev lst)
  (if (null? lst)
      '()
      (cons (car (last lst))
            (rev (butlast lst)))))

这里是last和butlast的定义。如果它们不是你的默认环境的一部分，那么似乎它们对于这个任务没有什么帮助，但是当你刚开始学习时，阅读并思考许多递归过程是很有好处的。

(define (butlast lst)
  (if (or (null? lst) (null? (cdr lst)))
      '()
      (cons (car lst) (butlast (cdr lst)))))

(define (last lst)
  (if (or (null? lst) (null? (cdr lst)))
      lst
      (last (cdr lst))))

- jbm

---

我不知道，这让事情变得更加困难。不过，有一种方法可以在没有实际命令的情况下获取列表的最后一个元素，那就是调用（first（rev-list（rest x））），假设基本情况类似于我在示例中的情况。 - b33k3rz

你有这个过程的书面要求吗？这可能会帮助我们逐字阅读它们。 - jbm

只使用if、cons、first、rest、empty?（endp）或len，编写一个函数，接受一个列表（仅限输入），并将其反转。不允许使用辅助函数。我已经使用这些限制给出了swap-ends解决方案，它在概念上类似。我相信如果我理解了它的工作原理，我就能为reverse-list做类似的事情。 - b33k3rz