在計劃中追加反向列表

Question

我正在學習Scheme並希望編寫一個反轉給定列表的遞歸程序。

然而，在一個測試案例中，我注意到a (b c) e - >e (b c) a。

我想要得到的是a (b c) e - >e (c b) a。

這是我有：

(define (deep-reverse lst) 
(if (null? lst) 
    '() 
    (begin 
    (display (car lst)) 
    (display "\n") 
    (if (null? (cdr lst)) 
     '() 
     (append (deep-reverse (cdr lst)) (list (reverse (car lst)))) 
     ) //End of inner if 
))) //End of begin, outer if, define 

當我試圖運行與

（深反向「（1（BC）（AB）））

代碼

我收到：

1 
(b c) 
(a b) 
mcdr: contract violation 
expected: mpair? 
given: 1 

問題與(list (reverse (car lst)))，雖然在一個孤立的測試案例中，它工作正常。這導致我相信這個問題可能與追加有關。

預先感謝您。

編輯：去從(list (reverse (car lst)))到(reverse (list(car lst)))使代碼運行沒有錯誤，但沒有扭轉(a b)到(b a)。

Answer 1

正如錯誤信息所解釋的那樣，您的問題在於您正在嘗試顛倒數字。首先，讓我們刪除一些不必要的條件並調試程序中的東西，以達到這個更簡單的程序。讓我們一步步通過這個程序，看看發生了什麼事情：

(define (deep-reverse lst) 
    (if (null? lst) 
     '() 
     (append (deep-reverse (cdr lst)) (list (reverse (car lst)))))) 

我們先從

(deep-reverse '(1 (b c) (a b))) 

代的說法，我們得到

(if (null? '(1 (b c) (a b))) 
    '() 
    (append (deep-reverse (cdr '(1 (b c) (a b)))) 
      (list (reverse (car '(1 (b c) (a b))))))) 

由於病情#f，簡化爲

(append (deep-reverse (cdr '(1 (b c) (a b)))) 
       (list (reverse (car '(1 (b c) (a b)))))) 

要評估第一個參數，請首先找到cdr，然後在其上調用deep-reverse。我將跳過這裏的步驟，但您應該能夠輕鬆地測試它是否正常工作。

(append '((b a) (c b)) (list (reverse (car '(1 (b c) (a b)))))) 

下一步，我們評估car：

(append '((b a) (c b)) (list (reverse 1))) 

在這裏，我們看到的是什麼問題，我們不能扭轉單號！

的問題是，你的deep-reverse應該有遞歸兩種截然不同的行爲：

• 一個數字或符號，或其他非列表實體，沒有做任何事情，因爲它沒有任何意義反向名單上的一個號碼
• ，深扭轉它

有兩個原因，當前的程序並沒有這樣做正確：

• 它只對列表元素進行淺反轉;也就是說，它不會深扭轉'(((a b) (c d)) ((e f) (g h)))正確
• ，如果它曾經遇到一些或其他非列表，像一個符號

最簡單的解決方法是添加一個條件，以檢查它是否是一個失敗先試圖扭轉它，然後再試一下pair?。如果不是pair?，然後lst必須是nil（我們可能留下不變化）或一個非列表對象（我們也可以離開原樣）

(define (deep-reverse lst) 
    (if (pair? lst) 
     (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst)))) 
     lst)) 

最後，我要指出的是，我們在這裏使用的模式實際上是一個foldr模式。我們可以抽象掉這種模式與foldr：

(define (deep-reverse xs) 
    (cond ((pair? xs) 
     (foldr (lambda (x y) (append y (list (deep-reverse x)))) '() xs)) 
     (else xs))) 

但是我們也注意到，這是低效的，因爲append是昂貴的操作。修改算法尾遞歸一個清楚地表明，這其實是一個foldl：

(define (deep-reverse xs) 
    (cond ((pair? xs) 
     (foldl (lambda (x y) (cons (deep-reverse x) y)) '() xs)) 
     (else xs))) 

它是如何這樣的功能可能會被寫在典型的慣用方案，或由威爾·內斯指出，

(define (deep-reverse xs) 
    (cond ((pair? xs) (reverse (map deep-reverse xs))) 
     (else xs)))