Comment obtenir un sous-arbre par index?
Supposons que j'ai l'arbre suivant:
Dans mon programme, cet arbre est représenté en utilisant une liste: '(+ (* 5 6) (sqrt 3)).
Comment obtenir un sous-arbre par son index?
L'index doit commencer à partir de 0 et être la profondeur d'abord. Dans l'image ci-dessus, j'ai étiqueté tous les nœuds avec leur index pour le montrer.
Par exemple:
(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
J'ai essayé de mettre en œuvre subtreecomme ceci:
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
Cependant, cela ne traverse pas les sous-listes. C'est incorrect.
ÉDITER:
J'ai essayé de mettre subtreeen œuvre en utilisant le style de passage continu:
(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))))
Cela fonctionne correctement pour les arbres comme:
'(+ 1 2)'(+ (* 5 6) (sqrt 3))
Cependant, cela échoue pour les arbres comme:
'(+ 1 2 3)
Quel est le problème avec ma mise en œuvre?
Réponses
La manière de faire ceci sans constructions de contrôle velues est avec un ordre du jour.
Mais avant de faire cela, définissez des abstractions . Chaque fois que je regarde du code qui marche quelque chose qu'il appelle un «arbre» et qui est plein d'explicites car, cdretc., je dois m'empêcher de simplement démarrer à froid l'univers dans l'espoir d'en obtenir un meilleur. Si celui qui vous enseigne ne vous le dit pas, ayez des mots forts avec lui .
Voici quelques abstractions de la structure arborescente. Celles-ci sont particulièrement importantes car la structure arborescente est vraiment irrégulière: je veux pouvoir dire «donnez-moi les enfants de ce nœud» sur n'importe quel nœud: les feuilles ne sont que des nœuds sans enfants, pas quelque chose de spécial.
(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)
'()))
Maintenant quelques abstractions pour l'ordre du jour. Les ordres du jour sont représentés sous forme de listes, mais rien d'autre ne le sait bien sûr, et une mise en œuvre plus industrielle pourrait bien ne pas vouloir les représenter comme ça.
(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))
Maintenant, il est facile d'écrire une version purement itérative de la fonction (l'ordre du jour maintient la pile), sans toutes sortes de constructions de contrôle velues.
(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))))])))
Une chose à penser: que se passe-t-il si vous remplacez agenda-prependpar agenda-appenddans la fonction ci-dessus?
J'ai corrigé mon implémentation. Si vous savez comment améliorer cela ou comment mettre en œuvre subtreesans utiliser le style de passage continuation (CPS), veuillez poster une réponse. Je suis particulièrement intéressé par une implémentation non-CPS (et non-call / cc).
Utilisation du style de passage de continuation:
(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))))
Usage:
(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
Une approche, qui parcourt l'arborescence de manière récursive, avec un compteur qui suit le nombre actuel de nœuds visités. Chaque fois qu'avant loopest appelé avec l'enfant d'un nœud, le compteur est incrémenté, donc lorsque vous looprevenez après avoir parcouru un sous-arbre, le compteur reflète le nombre de nœuds d'arbre visités jusqu'à présent (c'est là que votre logique échoue). Il utilise une continuation de "sortie" pour court-circuiter le déroulement de la pile d'appels lorsque le nœud souhaité est trouvé, le renvoyant directement du plus profond de la récursivité.
(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)
Dialecte de régime de poulet; Je n'ai pas installé Racket. Toute conversion nécessaire est laissée à l’exercice du lecteur.
(on dirait que remplacer foldpar foldlest suffisant)
OK, voyons voir ... La structure générale de ces énumérations en profondeur d'abord est avec une pile explicitement maintenue (ou pour le classement en largeur d'abord, une file d'attente):
(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))))))
Cela fait quelque chose de similaire mais pas exactement ce que vous vouliez:
> (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)))
Selon votre exemple, vous souhaitez ignorer le premier élément des applications:
(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))))))
pour que maintenant, comme tu le voulais,
> (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)))