如何僅使用基本操作遞歸地反轉列表？

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