爲什麼list-ref無法獲得正確的參數？

我寫了一個快速排序的方案（球拍）爲什麼list-ref無法獲得正確的參數？

#lang racket 

(define (quick-sort xs) 
    (let* ([p (list-ref xs 0)] 
     [tail (list-tail xs 1)] 
     [less (filter (lambda (x) (< x p)) tail)] 
     [greater (filter (lambda (x) (>= x p)) tail)]) 
    (append (quick-sort less) (list p) (quick-sort greater))))

但是，當我嘗試了，我得到這個錯誤：

> (quick-sort (list 99 2 9922)) 
list-ref: index 0 too large for list: '()

我新的計劃，所以我不太明白爲什麼列表裁判不能得到正確的輸入'(99 2 9922)

編輯：

感謝。我做到了。

#lang racket 

(define (quick-sort xs) 
    (let* ([p (first xs)] 
     [tail (rest xs)] 
     [less (filter (lambda (x) (< x p)) tail)] 
     [greater (filter (lambda (x) (>= x p)) tail)]) 
    (if (equal? (length xs) 1) 
     xs 
     (append (quick-sort less) (list p) (quick-sort greater)))))

來源

2011-07-29 ablmf

在你的新代碼中，每個輸入都測試了'（equal？（length xs）1）'，它總是計算xs的全部長度（一個線性運算）。既然你不關心長度是多少，除非它是1，你可以使用像'（和（not（null？xs））（null？（cdr xs）））'這樣的常量測試。（我建議斷言該列表不是空的，並且第一個元素*之後的部分*爲空，後者顯然意味着長度爲1，但會導致錯誤，除非該列表非空，因此是第一個條件。） – Carlo

當設計一個遞歸算法，有兩點是至關重要的：你的終止條件和您的遞歸步驟，和你沒有終止條件。跟蹤你的代碼是這樣做的：在你的quick-sort第一次執行，你會叫：

(append (quick-sort (list 2)) (list 99) (quick-sort (list 9922)))

而且第一quick-sort通話將依次調用(quick-sort '())。您的代碼不會非常優雅地處理空列表，因爲它始終會嘗試引用數組的第一個元素作爲第一個元素。

添加邏輯以優雅地處理空列表。

此外，使用first和rest來獲得列表的第一個和其餘元素被認爲更實用。

來源

2011-07-29 03:56:39 yan

當輸入列表爲空時，您的代碼缺少基本大小寫。當發生這種情況時，list-ref失敗並出現該錯誤。

BTW，請注意(list-ref l 0)一個更好的名字是(first l)，同樣(list-tail l 1)更好寫成(rest l)。

（還有car和cdr，但如果你是一個新手，你可以忽略它們了。）

來源

2011-07-29 03:56:19

您可能已經知道這一點，但是Racket也有一個內置的sort功能。

來源

2011-08-20 03:48:51 dyoo

爲什麼list-ref無法獲得正確的參數？

回答

相關問題