为什么list-ref不能得到正确的参数？

Question

我写了一个快速排序的方案(球拍)

#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: '()

我是方案的新手，所以我不太明白为什么list-ref不能获得正确的输入'(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)))))

Answer 1

在设计递归算法时，有两件事是至关重要的:终止条件和递归步骤，并且没有终止条件。跟踪您的代码正在做什么:在第一次执行quick-sort时，您将调用：

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

第一个quick-sort调用将依次调用(quick-sort '())。您的代码不能很好地处理空列表，因为它将始终尝试引用数组的第一个元素作为第一件事。

添加逻辑以优雅地处理空列表。

此外，使用first和rest来获取列表的第一个元素和剩余元素被认为更加实用。

Answer 2

当输入列表为空时，您的代码缺少基本大小写。当发生这种情况时，list-ref会失败，并返回该错误。

顺便说一句，请注意，(list-ref l 0)的更好名称是(first l)，类似地，(list-tail l 1)写成(rest l)更好。

(还有car和cdr，但如果你是新手，你可以暂时忽略它们。)

Answer 3

您可能已经知道这一点，但是Racket也附带了一个内置的sort函数。