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

Question

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

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

Вот мой сеанс Scheme от 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)

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

(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))

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

Answer 2

В быстрой сортировке удалите (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 странно, мне не нужно начинать, и мы можем продолжить.

Просто примечание, Chez Scheme оценит содержимое оператора начала по порядку. На языке программирования схем в нижней части страницы написано:

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