如何仅使用基本操作递归地反转列表？

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

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] -/ 

到目前为止，它确实交换了列表的结束元素。让我们从自然感应证明这一点，

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）-length列表的假设下，将扭转的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输入列表的一部分，然后将其反向并添加最后一个元素。 简单。 :)

Answer 2

你有没有在您的环境last和butlast？如果是这样，则程序可以这样定义（虽然奥斯卡指出，这是不是你通常会想办法的问题）：

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

Answer 3

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