Схема быстрой сортировки - Исключение: попытка применить не-процедуру (1 2 3 4 5 7 ...)

Question

Я только начал изучать Схему (схема Petite Chez) и как вызов себе. Я пытаюсь реализовать quicksort. Однако я получаю следующее исключение, когда я запускаю его:

Exception: attempt to apply non-procedure (1 2 3 4 5 7 ...) 

Вот моя схема сеанса с Emacs:

Petite Chez Scheme Version 8.4 
Copyright (c) 1985-2011 Cadence Research Systems 

> (define (set a i k) 
    (define (reduce-list a i n) 
     (if(= i n) 
    a 
    (reduce-list (cdr a) (+ i 1) n))) 
    (if(= i 0) 
     (cons k (cdr a)) 
     (let ((b (cons k (reduce-list a 0 (+ i 1))))) 
    (let push-front ((lst b) (original-list a) (n (- i 1))) 
     (if(<= n 0) 
      (cons (list-ref original-list 0) lst) 
      (push-front (cons (list-ref original-list n) lst) original-list (- n 1))))))) 

(define (swap lst i j) 
    (let ((a (list-ref lst i)) 
     (b (list-ref lst j))) 
     (set (set lst i b) j a))) 

(define (partition a i j r) 
    (cond [(= j r) (cons (+ i 1) (swap a (+ i 1) j))] 
     [(<= (list-ref a j) (list-ref a r)) (partition (swap a j (+ i 1)) (+ i 1) (+ j 1) r)] 
     [else (partition a i (+ j 1) r)])) 

(define (quicksort a p r) 
    (if(< p r) 
     (begin(
      (let* ((c (partition a (- p 1) p r)) 
      (q (car c)) 
      (b (quicksort (cdr c) p (- q 1)))) 
     (quicksort b (+ q 1) r)))) 
     a)) 

> (define lst (list 1 9 2 8 3 7 4 6 5)) 
> (define n (length lst)) 
> (trace quicksort) 
(quicksort) 
> (quicksort lst 0 (- n 1)) 
|(quicksort (1 9 2 8 3 7 4 6 5) 0 8) 
| (quicksort (1 2 3 4 5 7 8 6 9) 0 3) 
| |(quicksort (1 2 3 4 5 7 8 6 9) 0 2) 
| | (quicksort (1 2 3 4 5 7 8 6 9) 0 1) 
| | |(quicksort (1 2 3 4 5 7 8 6 9) 0 0) 
| | |(1 2 3 4 5 7 8 6 9) 
| | |(quicksort (1 2 3 4 5 7 8 6 9) 2 1) 
| | |(1 2 3 4 5 7 8 6 9) 
Exception: attempt to apply non-procedure (1 2 3 4 5 7 ...) 
> 

Может кто-нибудь сказать мне, что происходит не так? Спасибо заранее

Answer 1

Проблема заключается с

begin 

в быстрой сортировке. Когда

(quicksort b (+ q 1) r) 

в конце концов возвращает (который на самом деле б в родительской сортировке), то пусть * блок уменьшается от

(define (quicksort a p r) 
    (if(< p r) 
    (begin(
      (let* ((c (partition a (- p 1) p r)) 
        (q (car c)) 
        (b (quicksort (cdr c) p (- q 1)))) 
       (quicksort b (+ q 1) r)))) 
    a)) 

в

(define (quicksort a p r) 
    (if(< p r) 
    (begin 
     (b)) ;this is the cause of the error 
    a)) 

А поскольку б список , пытаясь вызвать его с ошибкой. Если вы удалите начало, блок let будет вести себя так, как вы намереваетесь.

Answer 2

В quicksort удалите (begin( и последние ) на линии (quicksort b (+ q 1) r).

( после begin и ) на линии быстрой сортировки применяют результат этого второго быстросохнущего вызова.

Это потому, что это последнее выражение в теле let*, поэтому это возвращаемое значение let *. Список, который он возвращает, - это список, который определенно не является процедурой.

Кроме того, у всех есть неявное начало в них.

Например

(let ([a 1] [b 2] [c 3]) 
    (set! b 3) 
    a 
    b) 

вернуть бы 3 (равнину вызов является бесполезным и его значение игнорируется)

И это эквивалентно следующему коду:

(let ([a 1] [b 2] [c 3]) 
    (begin 
    (set! b 3) 
    a 
    b)) 

Answer 3

Поскольку другие ответили на ваш вопрос, я хотел бы прояснить что-то, отсутствующее в других ответах, которые, надеюсь, помогут вам и/или другим людям с их пониманием (begin()).

Я обычно использую (begin()), как вы это делали в операциях (if()), потому что функция имеет только два слота после условного.

Таким образом, (begin()) становится полезным, когда намерен оценить несколько операторов для одной или обеих сторон условной «раскола в дороге», по себе.

Пример:

(do ([i 0 (+ i 1)]) [(< i 10)] 
    (if (= (% i 2) 1) 
    (printf 'odd) 
    (begin 
     (printf 'even) 
     'even))) 

Выше я использую только (begin()) когда я хочу Chez выполнять два отдельных действия, если число i даже. Когда i нечетно, мне не нужен оператор begin, и мы можем продолжить.

Только примечание, Chez Scheme будет оценивать содержимое инструкции начала в порядке. В The Scheme Programming Language, он говорит, что в нижней части страницы:

«Синтаксическая форма начать [...] оценивает свои подвыражения в последовательности слева направо и возвращает значение последнего подвыражения, как тело let или лямбда-выражения ».