Wie höre ich die Rekursion auf und gebe etwas im Racket zurück?

Question

HINWEIS: Ich würde dies gerne tun, ohne Rackets in Ausnahmen gebaut, wenn möglich.

Ich habe viele Funktionen, die andere Funktionen aufrufen und rekursiv auf die ursprüngliche Funktion zurückrufen können. Unter bestimmten Bedingungen auf dem Weg möchte ich weitere rekursive Schritte stoppen, und keine anderen Funktionen mehr aufrufen und einfach einen Wert/String zurückgeben (der Stack kann ignoriert werden, wenn die Bedingung erfüllt ist) .. hier ist ein künstliches Beispiel, das hoffentlich zeigen, was ich versuche zu erreichen:

(define (add expr0 expr1) 
(cond 
[(list? expr0) (add (cadr expr0) (cadr (cdr expr0)))] 
[(list? expr1) (add (cadr expr1) (cadr (cdr expr1)))] 
[else (if (or (equal? expr0 '0) (equal? expr1 '0)) 
     '(Adding Zero) 
     (+ expr0 expr1))] 
)) 

Wenn dies meine Funktion ist und ich nannte es mit (add (hinzufügen 2 0) 3), dann das Ziel wäre, einfach die gesamte Zeichenfolge zurück ' (Hinzufügen von Null) ANYTIME, dass eine Null ist einer der Ausdrücke, anstatt den rekursiven Aufruf an (add '(Adding Zero) 3)

Gibt es eine Möglichkeit, im Wesentlichen aus der Rekursion "zu brechen"? Mein Problem ist, dass, wenn ich schon tief drinnen bin, es irgendwann versuchen wird, "(Zero hinzufügen) auszuwerten, was es nicht weiß, und ich habe das Gefühl, dass ich das tun könnte, ohne jedem einen expliziten Check zu machen expr ..

Jede Führung wäre großartig.

Answer 1

In Ihrem speziellen Fall müssen Sie nicht von der normalen Verarbeitung "flüchten". Wenn Sie einfach '(Adding Zero) in der Endposition haben, wird Ihre add-Funktion (Adding Zero) zurückgeben.

Um eine Situation zu schaffen, in dem man entkommen könnte müssen, Sie etwas ein wenig komplizierter brauchen:

(define (recursive-find/collect collect? tree (result null)) 
    (cond ((null? tree) (reverse result)) 
      ((collect? tree) (reverse (cons tree result))) 
      ((not (pair? tree)) (reverse result)) 
      (else 
      (let ((hd (car tree)) 
        (tl (cdr tree))) 
       (cond ((collect? hd) 
        (recursive-find/collect collect? tl (cons hd result))) 
        ((pair? hd) 
        (recursive-find/collect collect? tl 
           (append (reverse (recursive-find/collect collect? hd)) result))) 
        (else (recursive-find/collect collect? tl result))))))) 

Sie die Verarbeitung abbrechen Angenommen wollte und nur 'Hahaha! zurück, wenn jeder Knoten im Baum den Wert hatte 'Joker. Nur 'Hahaha! in Heckposition zu bewerten wäre nicht genug, weil recursive-find/collect nicht immer in Endposition verwendet wird.

Schema bietet Fortsetzungen für diesen Zweck. Der einfachste Weg, es in meinem speziellen Beispiel zu tun wäre, um die Fortsetzung der Prädikatfunktion zu verwenden, wie folgt aus:

(call/cc 
    (lambda (continuation) 
    (recursive-find/collect 
     (lambda (node) 
      (cond ((eq? node 'Joker) 
        (continuation 'Hahaha!)) ;; Processing ends here 
        ;; Otherwise find all the symbols 
        ;; in the tree 
        (else (symbol? node)))) 
     '(Just 1 arbitrary (tree (stucture) ((((that "has" a Joker in it))))))))) 

Eine Fortsetzung repräsentiert „den Rest der Berechnung“, die nach dem call/cc Block passieren werden endet. In diesem Fall gibt es nur eine Möglichkeit, aus dem call/cc Block von irgendwo im Stapel zu entkommen.

Aber Fortsetzungen haben auch andere seltsame Eigenschaften, wie zum Beispiel erlaubt Ihnen, zurück zu welchem ​​Block des Codes zu springen, der call/cc erscheint, selbst nachdem die Ausführung diesen Teil des Programms verlassen hat. Zum Beispiel:

(define-values a b (call/cc 
        (lambda (cc) 
         (values 1 cc)))) 
(cc 'one 'see-see) 

In diesem Fall cc Aufruf springt zurück zum define-values Form und definiert a und b-one und see-see sind.

Schläger hat auch "Escape-Fortsetzungen" (call/ec oder let/ec), die aus ihrer Form entkommen können, aber nicht zurück springen können. Im Gegenzug für diese Einschränkung erhalten Sie eine bessere Leistung.