Jak uzyskać poddrzewo według indeksu?
Załóżmy, że mam następujące drzewo:
W moim programie, to drzewo jest reprezentowany na podstawie listy: '(+ (* 5 6) (sqrt 3)).
Jak uzyskać poddrzewo według jego indeksu?
Indeks powinien zaczynać się od 0 i zaczynać się od głębokości. Na powyższym obrazku oznaczyłem wszystkie węzły ich indeksem, aby to pokazać.
Na przykład:
(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
Próbowałem zaimplementować w subtreeten sposób:
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
Jednak nie prowadzi to do podlist. To jest niepoprawne.
EDYTOWAĆ:
Próbowałem zaimplementować subtreeużywając stylu przekazywania kontynuacji:
(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))))
Działa to poprawnie w przypadku drzew takich jak:
'(+ 1 2)'(+ (* 5 6) (sqrt 3))
Jednak zawodzi w przypadku drzew takich jak:
'(+ 1 2 3)
Co jest nie tak z moją implementacją?
Odpowiedzi
Sposobem na zrobienie tego bez włochatych konstruktów kontrolnych jest program.
Ale zanim to zrobisz, zdefiniuj abstrakcje . Za każdym razem, gdy patrzę na kod, który porusza się po czymś, co nazywa się „drzewem” i jest pełen wyraźnych informacji car, cdrmuszę powstrzymać się przed uruchomieniem wszechświata na zimno w nadziei, że uda nam się uzyskać lepszy. Jeśli ten, kto cię uczy, nie mówi ci tego, miej z nim mocne słowa .
Oto kilka abstrakcji dotyczących struktury drzewa. Są one szczególnie ważne, ponieważ struktura drzewa jest naprawdę nieregularna: chcę móc powiedzieć „daj mi dzieci tego węzła” na dowolnym węźle: liście są po prostu węzłami bez dzieci, a nie jakimś szczególnym rodzajem rzeczy.
(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)
'()))
Teraz kilka abstrakcji do porządku obrad. Agendy są przedstawiane jako listy, ale nic innego oczywiście o tym nie wie, a bardziej przemysłowa implementacja może nie chcieć ich tak przedstawiać.
(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))
Teraz łatwo jest napisać czysto iteracyjną wersję funkcji (celem jest utrzymanie stosu), bez wszelkiego rodzaju włochatych konstrukcji kontrolnych.
(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))))])))
Rzecz do przemyślenia: co się stanie, jeśli w powyższej funkcji zastąpisz agenda-prependprzez agenda-append?
Naprawiłem swoją implementację. Jeśli wiesz, jak to poprawić lub wiesz, jak wdrożyć subtreebez używania stylu przekazywania kontynuacji (CPS), napisz odpowiedź. Szczególnie interesuje mnie implementacja bez CPS (i bez wywołania / cc).
Korzystanie ze stylu przekazywania kontynuacji:
(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))))
Stosowanie:
(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
Jedno podejście, które rekurencyjnie porusza się po drzewie, z licznikiem, który śledzi aktualną liczbę odwiedzonych węzłów. Za każdym razem, gdy loopwywoływana jest wcześniej z dzieckiem węzła, licznik jest zwiększany, więc gdy looppowraca z przechodzenia po poddrzewie, licznik odzwierciedla liczbę odwiedzonych dotąd węzłów drzewa (co jest przyczyną niepowodzenia logiki). Używa kontynuacji „wyjścia” do zwarcia rozwijającego stos wywołań, gdy żądany węzeł zostanie znaleziony, bezpośrednio zwracając go z głębi rekurencji.
(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)
Dialekt systemu kurczaka; Nie mam zainstalowanej rakiety. Wszelkie potrzebne nawrócenia pozostawiamy jako ćwiczenie dla czytelnika.
(wygląda jak zastąpienie foldze foldlwystarczy)
OK, zobaczmy ... Ogólna struktura takich wyliczeń w pierwszej kolejności jest z jawnie utrzymywanym stosem (lub kolejką w przypadku kolejności od początku wszerz):
(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))))))
To robi coś podobnego, ale nie dokładnie tego, czego chciałeś:
> (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)))
Jak na twoim przykładzie chcesz pominąć pierwszy element w aplikacjach:
(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))))))
więc teraz, jak chciałeś,
> (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)))