Schema Quicksort - Ausnahme: Versuch, Nicht-Verfahren anzuwenden (1 2 3 4 5 7 ...)

Question

Ich habe gerade angefangen, Scheme (Petite Chez Scheme) zu lernen und als eine Herausforderung für mich versuche ich Quicksort zu implementieren. Allerdings erhalte ich die folgende Ausnahme, wenn ich es laufen:

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

Hier ist meine Scheme-Sitzung von 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 ...) 
> 

Kann mir jemand sagen, was falsch läuft? Vielen Dank im Voraus

Answer 1

Das Problem ist, mit dem

begin 

in quicksort. Wenn

(quicksort b (+ q 1) r) 

schließlich eine zurückgibt (die eigentlich b in der Mutter quicksort ist), dann reduziert sich die let * Block von

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

zu

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

da b Und ist eine Liste , versucht, es aufzurufen, schlägt mit einem Fehler fehl. Wenn Sie den Beginn entfernen, verhält sich der Let-Block wie beabsichtigt.

Answer 2

In Quicksort entfernen Sie die (begin( und die letzte ) auf der (quicksort b (+ q 1) r) Linie.

Die ( nach der begin und die ) auf der Quicksort-Anruf-Leitung sind das Ergebnis dieses zweiten Quicksort-Aufrufs.

Dies ist, weil es der letzte Ausdruck im Körper der let* ist, so ist es der Rückgabewert des Let *. Die Liste, die zurückgegeben wird, ist die Liste, die definitiv keine Prozedur ist.

Auch alle haben wir einen impliziten Beginn in ihnen.

Zum Beispiel

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

Würde wieder 3 (die Ebene ein Anruf eines wertlos und sein Wert wird ignoriert)

Und es entspricht den folgenden Code:

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

Answer 3

Da andere die Antwort auf Ihre Frage angegeben haben, möchte ich etwas klären, das in den anderen Antworten fehlt, das Ihnen und/oder anderen mit ihrem Verständnis vonhoffentlich helfen wird.

Ich verwende am häufigsten (begin()) wie Sie in (if()) Anweisungen getan, weil die Funktion nur zwei Steckplätze nach der bedingten hat.

Somit wird die (begin()) nützlich, wenn die Absicht hat mehrere Anweisungen für einen oder beiden Seiten der bedingten „Spaltung in der Straße“, per se zu bewerten.

Ein Beispiel:

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

Above ich nur (begin()) verwenden, wenn ich Chez wollen zwei getrennte Aktionen auszuführen, wenn die Zahl i selbst ist. Wenn i ungerade ist, brauche ich keine Anfangserklärung und wir können weitermachen.

Nur eine Notiz, Chez Scheme wird den Inhalt der Begin-Anweisung in der Reihenfolge auswerten. In The Scheme Programming Language, heißt es am unteren Rand der Seite:

„Die syntaktische Form beginnen [...] seine Teilausdrücke in Sequenz auswertet von links nach rechts und gibt den Wert des letzten subexpression, wie der Körper eines Let- oder Lambda-Ausdrucks. "