Rückgabeliste mit Rekursion mit Racket

Question

Ich versuche, eine Liste (BST, ein binärer Suchbaum) von einer Methode zurückzugeben, die doppelte Rekursion hat. Ich versuche es wie folgt umzusetzen:

(define (mapBST BST someFunct) 
    (cond 
    [(null? BST) 
    '()] 
     [else (cons (car BST) (someFunct (car (cdr BST)))) (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct) ] 

) 
) 

Das mit diesem kleinen Code-Schnipsel

(define bst 
      '(3 "3" 
        (1 "1" 
        () 
        (2 "2"()()) 
       ) 
        (5 "5"()()) 
      ) 
) 
(mapBST bst string->number) 

Ich habe auch versucht, diese Schnipsel aufgerufen wird, aber es zurück ((()())()):

[else (printf (car (cdr BST))) (cons (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct)) ] 

Die Ergebnis sollte die gleiche BST zurückgeben, aber mit Nummer anstelle von String als Wert.

Answer 1

Innerhalb Ihres else-Ausdrucks rekonstruieren Sie den binären Suchbaum nicht richtig, weshalb Sie eine leere Liste erhalten. Ändern Sie Ihre else Fall

... 
[else 
(cons (car BST) 
     (cons (someFunct (car (cdr BST))) 
      (cons (mapBST (car (cdr (cdr BST))) someFunct) 
        (cons (mapBST (car (cdr (cdr (cdr BST)))) someFunct) empty))))] 
... 

oder

... 
[else 
(list (car BST) 
     (someFunct (car (cdr BST))) 
     (mapBST (car (cdr (cdr BST))) someFunct) 
     (mapBST (car (cdr (cdr (cdr BST)))) someFunct))] 
... 

wird Ihr Problem beheben (beide Optionen produzieren die gleiche Liste, da (cons 1 (cons 2 empty))-(list 1 2) entspricht).

Hier ist eine vollständige Aktualisierung von mapBST ist:

(define (mapBST proc BST) 
    (cond 
    [(null? BST) empty] 
    [else 
    (list (car BST) 
      (proc (cadr BST)) 
      (mapBST proc (caddr BST)) 
      (mapBST proc (cadddr BST)))])) 

Zum Beispiel

(define BST '(3 "3" (1 "1"() (2 "2"()())) (5 "5"()()))) 
(mapBST string->number BST) 
=> '(3 3 (1 1() (2 2()())) (5 5()())) 

Answer 2

Wie in einer anderen Antwort darauf hingewiesen, Sie kehren nicht eigentlich das, was Sie denken, Sie in der else Klausel sind . Behebung, dass Ihr Programm funktioniert. Allerdings ist diese Art von (car (cdr (cdr ...))) Sache, wie die Leute in den 1960er Jahren Lisp zu schreiben, und es hat Lisp zu Recht einen schlechten Namen, weil es völlig undurchsichtig ist. Dinge wie caddr zu benutzen ist besser, aber nur leicht (und wie viele von ihnen bietet die Sprache? Ich kann mich nie erinnern). Noch besser, wenn Ihre Daten konzeptionell eine Liste ist, ist wie secondfirst & mit Namen Funktionen zu verwenden, weil sie sagen, was man eigentlich bedeutet (wenn Ihre Daten vom Konzept her ein Baum von conses ist, dann car & c ist besser wahrscheinlich). Aber sie haben immer noch das Problem "Wie viele von ihnen gibt es diese Woche".

Die richtige Lösung ist die Destrukturierung &/oder Mustererkennung, um Variablen an die Form Ihrer Daten zu binden. Das macht deinen Code wirklich klar. Racket hat hierfür einen umfassenden Mechanismus, den ich nicht wirklich im Detail verstehe, aber ich weiß genug, um mich durchzubringen. Hier ist (a fixed) Version Ihrer Funktion, die match verwendet die Arbeit zu tun:

(define (map-bst bst fn) 
    (match bst 
    ['() '()] 
    [(list 1st 2nd 3rd 4th) 
    (list 1st 
      (fn 2nd) 
      (map-bst 3rd fn) 
      (map-bst 4th fn))] 
    [_ (error "botch")])) 

(beachten Sie, dies mit einer besseren Variablennamen tun konnte: Ich weiß nicht, was die verschiedenen Bits der Struktur bedeuten).