Почему 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 .