扭轉列表錯誤

Question

我正在學習DrRacket，而且我需要編寫一個反轉列表的程序。我有下面的內容，它正在倒轉數字，但不知何故將它們嵌套在列表或其他內容中。的

(define (reverse-list lon) 
    (if (empty? lon) 
     empty 
     (cons (reverse-list (rest lon)) 
      (cons (first lon) 
        empty)))) 

輸出（反向列表（列表1 2 3 4））：

(list (list (list (list empty 4) 3) 2) 1) 

任何人都知道爲什麼輸出不僅僅是出來作爲一個列表？

感謝您的幫助！

Answer 1

所以，最後工作的只是用一個append替換第一個cons來停止列表嵌套。

(define (reverse-list lon) 
    (if (empty? lon) empty (append (reverse-list (rest lon)) (cons (first lon) empty)))) 

問題解決了，謝謝你的幫忙。

Answer 2

A cons有兩個單元格。 car和cdr。一個單元可以顯示爲(a . b)，其中a和b可以是任何東西。

有一對替代表示。如果b是另一對或空列表，則可以將. b)替換爲b，而不是最初的(。因此：

(a .())    ; ==> (a) 
(a . (b . c))  ; ==> (a b . c) 
(a . (b . (c .()))) ; ==> (a b c) 

現在爲您的代碼。想象一下你用(1 2 3 4)（或準確的說是(1 . (2 . (3 . (4 .()))))）來試試。我們使用substitution rules準確計算您的程序的功能：

(reverse-list '(1 . (2 . (3 . (4 .())))))     ; ==> 
(if (empty? '(1 . (2 . (3 . (4 .()))))) 
    empty 
    (cons (reverse-list (rest '(1 . (2 . (3 . (4 .())))))) 
      (cons (first '(1 . (2 . (3 . (4 .()))))) 
       empty)))          ; ==> 
(if #f 
    empty 
    (cons (reverse-list (rest '(1 . (2 . (3 . (4 .())))))) 
      (cons (first '(1 . (2 . (3 . (4 .()))))) 
       empty)))          ; ==> 

(cons (reverse-list '(2 . (3 . (4 .())))) 
     (cons 1 empty))          ; ==> 

(cons (cons (reverse-list '(3 . (4 .()))) 
      (cons 2 empty)) 
     (cons 1 empty))          ; ==> 

(cons (cons (cons (reverse-list '(4 .())) 
        (cons 3 empty)) 
      (cons 2 empty)) 
     (cons 1 empty))          ; ==> 

(cons (cons (cons (cons (reverse-list '()) 
         (cons 4 empty)) 
        (cons 3 empty)) 
      (cons 2 empty)) 
     (cons 1 empty))          ; ==> 

(cons (cons (cons (cons '() 
         (cons 4 empty)) 
        (cons 3 empty)) 
      (cons 2 empty)) 
     (cons 1 empty))          ; ==> 

((((() . (4 .())) . (3 .())) . (2 .())) . (1 .()))  ; ==> 
((((() . (4)) . (3)) . (2)) . (1))       ; ==> 
((((() 4) 3) 2) 1) 

現在。一個真正的逆轉列表看起來會是這樣的點分表示法：

(4 . (3 . (2 . (1 .())))) ; ==> (4 3 2 1) 

有沒有辦法解決它。您需要與cons保持密切關係，並瞭解如何顯示構建它們的不同方式。一個提示是，幾乎每個列表都從頭到尾創建，並從頭到尾迭代。

Answer 3

很高興看到你已經解決了你自己的問題。不過，我覺得我應該選擇一點，因爲反轉列表真的是在迭代中建立一個列表。

(define (reverse-list lon) 
    ;; iterative helper procedure 
    (define (aux lon acc) 
    (if (empty? lon) 
     acc 
     (aux (rest lon) 
      (cons (first lon) acc)))) 
    ;; use helper 
    (aux lon empty)) 

(reverse-list '(1 2 3 4)) ; ==> (4 3 2 1) 

正如你可以看到，我們從開始到結束迭代。當我們這樣做時，我們會將當前元素放到累積列表中，並且操作從頭到尾。 E.I.最後添加的元素將成爲結果中的第一個元素。關於這一點的好處是，我們爲每個處理過的單元使用一個新的單元，並且它已成爲最終結果的一部分。對於append的每次使用，您都複製第一個參數，以便n元素列表獲得分配不必要的單元格的(apply + (range n))。

一個更豐富的策士會使用一個名爲let做到既本地過程和一氣呵成撥打：

(define (reverse-list lon) 
    (let aux ((lon lon) (acc empty)) 
    (if (empty? lon) 
     acc 
     (aux (rest lon) 
      (cons (first lon) acc)))))