Wie erhalte ich einen Teilbaum nach Index?
Angenommen, ich habe den folgenden Baum:
In meinem Programm wird dieser Baum anhand einer Liste dargestellt : '(+ (* 5 6) (sqrt 3)).
Wie erhalte ich einen Teilbaum anhand seines Index?
Der Index sollte bei 0 beginnen und an erster Stelle stehen. Im obigen Bild habe ich alle Knoten mit ihrem Index beschriftet, um dies zu zeigen.
Zum Beispiel:
(define tree '(+ (* 5 6) (sqrt 3)))
(subtree tree 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1) ; Returns: '(* 5 6)
(subtree tree 2) ; Returns: 5
(subtree tree 3) ; Returns: 6
(subtree tree 4) ; Returns: '(sqrt 3)
(subtree tree 5) ; Returns: 3
Ich habe versucht, so zu implementieren subtree:
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
Dies führt jedoch nicht zu Unterlisten. Es ist falsch.
BEARBEITEN:
Ich habe versucht, subtreemit Continuation-Passing-Stil zu implementieren :
(define (subtree& exp index counter f)
(cond [(= counter index) exp]
[(null? exp) (f counter)]
[(list? exp)
(let ((children (cdr exp)))
(subtree& (car children)
index
(+ counter 1)
(lambda (counter2)
(if (null? (cdr children))
(f counter)
(subtree& (cadr children)
index
(+ counter2 1)
f)))))]
[else (f counter)]))
(define (subtree tree index)
(subtree& tree
index
0
(lambda (_)
(error "Index out of bounds" index))))
Dies funktioniert korrekt für Bäume wie:
'(+ 1 2)'(+ (* 5 6) (sqrt 3))
Es scheitert jedoch bei Bäumen wie:
'(+ 1 2 3)
Was ist falsch an meiner Implementierung?
Antworten
Der Weg, dies ohne haarige Kontrollkonstrukte zu tun, ist mit einer Agenda.
Aber bevor Sie das tun, definieren Sie Abstraktionen . Jedes Mal , wenn ich Code suchen , die etwas zu Fuß ist es nennt einen ‚Baum‘ und ist voll von expliziten car, cdrusw Ich habe mich daran zu hindern, einfach das Universum in der Hoffnung , kalt Boote bekommen wir einen besseren. Wenn jemand, der Sie unterrichtet, Ihnen dies nicht sagt, haben Sie starke Worte mit ihnen .
Hier sind einige Abstraktionen für die Baumstruktur. Diese sind besonders wichtig, weil die Baumstruktur wirklich unregelmäßig ist: Ich möchte auf jedem Knoten sagen können: "Gib mir die Kinder dieses Knotens": Blätter sind nur Knoten ohne Kinder, keine besondere Sache.
(define (make-node value . children)
;; make a tree node with value and children
(if (null? children)
value
(cons value children)))
(define (node-value node)
;; the value of a node
(if (cons? node)
(car node)
node))
(define (node-children node)
;; the children of a node as a list.
(if (cons? node)
(cdr node)
'()))
Nun einige Abstraktionen für die Agenda. Agenden werden als Listen dargestellt, aber nichts anderes weiß dies natürlich, und eine industriellere Implementierung möchte sie möglicherweise nicht so darstellen.
(define empty-agenda
;; an empty agenda
'())
(define agenda-empty?
;; is an agenda empty?
empty?)
(define (agenda-next agenda)
;; return the next element of an agenda if it is not empty
;; error if it is
(if (not (null? agenda))
(car agenda)
(error 'agenda-next "empty agenda")))
(define (agenda-rest agenda)
;; Return an agenda without the next element, or error if the
;; agenda is empty
(if (not (null? agenda))
(cdr agenda)
(error 'agenda-rest "empty agenda")))
(define (agenda-prepend agenda things)
;; Prepend things to agenda: the first element of things will be
;; the next element of the new agenda
(append things agenda))
(define (agenda-append agenda things)
;; append things to agenda: the elements of things will be after
;; all elements of agenda in the new agenda
(append agenda things))
Jetzt ist es einfach, eine rein iterative Version der Funktion zu schreiben (die Agenda verwaltet den Stapel), ohne alle möglichen haarigen Kontrollkonstrukte.
(define (node-indexed root index)
;; find the node with index index in root.
(let ni-loop ([idx 0]
[agenda (agenda-prepend empty-agenda (list root))])
(cond [(agenda-empty? agenda)
;; we're out of agenda: raise an exception
(error 'node-indexed "no node with index ~A" index)]
[(= idx index)
;; we've found it: it's whatever is next on the agenda
(agenda-next agenda)]
[else
;; carry on after adding all the children of this node
;; to the agenda
(ni-loop (+ idx 1)
(agenda-prepend (agenda-rest agenda)
(node-children
(agenda-next agenda))))])))
Denken Sie darüber nach: Was passiert, wenn Sie in der obigen Funktion agenda-prependdurch ersetzen agenda-append?
Ich habe meine Implementierung behoben. Wenn Sie wissen, wie Sie dies verbessern oder implementieren können, subtreeohne den Continuation-Passing-Stil (CPS) zu verwenden, geben Sie bitte eine Antwort. Ich bin besonders an einer Implementierung ohne CPS (und ohne Call / CC) interessiert.
Verwenden des Continuation-Passing-Stils:
(define (subtree& exp index counter f)
(cond [(= counter index) exp]
[(null? exp) (f counter)]
[(list? exp)
(define children (cdr exp))
(define (sibling-continuation siblings)
(lambda (counter2)
(if (null? siblings)
(f counter2)
(subtree& (car siblings)
index
(+ counter2 1)
(sibling-continuation (cdr siblings))))))
(subtree& (car children)
index
(+ counter 1)
(sibling-continuation (cdr children)))]
[else (f counter)]))
(define (subtree tree index)
(subtree& tree
index
0
(lambda (max-index)
(error "Index out of bounds" index))))
Verwendung:
(define t1 '(+ (* 5 6) (sqrt 3)))
(subtree t1 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree t1 1) ; Returns: '(* 5 6)
(subtree t1 2) ; Returns: 5
(subtree t1 3) ; Returns: 6
(subtree t1 4) ; Returns: '(sqrt 3)
(subtree t1 5) ; Returns: 3
(define t2 '(+ 0 (* (/ 1 2) (- 3 4)) (sqrt 5) 6))
(subtree t2 0) ; Returns: '(+ 0 (* (/ 1 2) (- 3 4)) (sqrt 5) 6)
(subtree t2 1) ; Returns: 0
(subtree t2 2) ; Returns: '(* (/ 1 2) (- 3 4))
(subtree t2 3) ; Returns: '(/ 1 2)
(subtree t2 4) ; Returns: 1
(subtree t2 5) ; Returns: 2
(subtree t2 6) ; Returns: '(- 3 4)
(subtree t2 7) ; Returns: 3
(subtree t2 8) ; Returns: 4
(subtree t2 9) ; Returns: '(sqrt 5)
(subtree t2 10) ; Returns: 5
(subtree t2 11) ; Returns: 6
Ein Ansatz, der rekursiv über den Baum läuft, mit einem Zähler, der die aktuelle Anzahl der besuchten Knoten verfolgt. Jedes Mal, wenn zuvor loopmit dem Kind eines Knotens aufgerufen wird, wird der Zähler inkrementiert. Wenn Sie also loopvom Gehen eines Teilbaums zurückkehren, gibt der Zähler die Anzahl der bisher besuchten Baumknoten wieder (wo Ihre Logik fehlschlägt). Es verwendet eine "Exit" -Fortsetzung, um den Aufrufstapel kurzzuschließen, wenn der gewünschte Knoten gefunden wurde, und ihn direkt aus der Tiefe der Rekursion zurückzugeben.
(require-extension (srfi 1))
(require-extension (chicken format))
(define (subtree tree idx)
(call/cc
(lambda (return-result)
(let loop ((node tree)
(n 0)) ; the counter
(cond
((= idx n) ; We're at the desired node
(return-result node))
((list? node) ; Node is itself a tree; recursively walk its children.
(fold (lambda (elem k) (loop elem (+ k 1))) n (cdr node)))
(else n))) ; Leaf node; return the count of nodes so far
;; return-result hasn't been called, so raise an error
(error "No such index"))))
(define (test tree depth)
(printf "(subtree tree ~A) -> ~A~%" depth (subtree tree depth)))
(define tree '(+ (* 5 6) (sqrt 3)))
(test tree 0)
(test tree 1)
(test tree 2)
(test tree 3)
(test tree 4)
(test tree 5)
Hühnchenschema Dialekt; Ich habe Racket nicht installiert. Jede erforderliche Konvertierung bleibt dem Leser als Übung überlassen.
(sieht aus wie das Ersetzen folddurch foldlist genug)
OK, mal sehen ... Die allgemeine Struktur solcher Tiefenaufzählungen besteht aus einem explizit gepflegten Stapel (oder für die Reihenfolge der Breite zuerst einer Warteschlange):
(define (subtree t i)
(let loop ((t t) (k 0) (s (list))) ; s for stack
(cond
((= k i) t) ; or: (append s (cdr t)) for a kind of
((pair? t) (loop (car t) (+ k 1) (append (cdr t) s))) ; bfs ordering
((null? s) (list 'NOT-FOUND))
(else (loop (car s) (+ k 1) (cdr s))))))
Dies macht etwas Ähnliches, aber nicht genau das, was Sie wollten:
> (map (lambda (i) (list i ': (subtree tree i))) (range 10))
'((0 : (+ (* 5 6) (sqrt 3)))
(1 : +)
(2 : (* 5 6))
(3 : *)
(4 : 5)
(5 : 6)
(6 : (sqrt 3))
(7 : sqrt)
(8 : 3)
(9 : (NOT-FOUND)))
Gemäß Ihrem Beispiel möchten Sie das erste Element in Anwendungen überspringen:
(define (subtree-1 t i) ; skips the head elt
(let loop ((t t) (k 0) (s (list))) ; s for stack
(cond
((= k i) t)
((and (pair? t)
(pair? (cdr t)));____ ____ ; the
(loop (cadr t) (+ k 1) (append (cddr t) s))) ; changes
((null? s) (list 'NOT-FOUND))
(else (loop (car s) (+ k 1) (cdr s))))))
so dass jetzt, wie Sie wollten,
> (map (lambda (i) (list i ': (subtree-1 tree i))) (range 7))
'((0 : (+ (* 5 6) (sqrt 3)))
(1 : (* 5 6))
(2 : 5)
(3 : 6)
(4 : (sqrt 3))
(5 : 3)
(6 : (NOT-FOUND)))