¿Cómo obtengo un subárbol por índice?
Supongamos que tengo el siguiente árbol:
En mi programa, este árbol está representado mediante una lista: '(+ (* 5 6) (sqrt 3)).
¿Cómo obtengo un subárbol por su índice?
El índice debe comenzar desde 0 y ser primero en profundidad. En la imagen de arriba, he etiquetado todos los nodos con su índice para mostrar esto.
Por ejemplo:
(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
Traté de implementar subtreeasí:
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
Sin embargo, esto no atraviesa las sublistas. Es incorrecto
EDITAR:
Intenté implementar subtreeusando el estilo de paso de continuación:
(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))))
Esto funciona correctamente para árboles como:
'(+ 1 2)'(+ (* 5 6) (sqrt 3))
Sin embargo, falla para árboles como:
'(+ 1 2 3)
¿Qué pasa con mi implementación?
Respuestas
La forma de hacer esto sin construcciones de control complicadas es con una agenda.
Pero antes de hacer eso, defina abstracciones . Cada vez que miro un código que es algo que camina, lo que llama un 'árbol' y está lleno de explícito car, cdretc., tengo que evitar simplemente arrancar en frío el universo con la esperanza de obtener uno mejor. Si quien le está enseñando no le dice esto, tenga palabras fuertes con él .
Aquí hay algunas abstracciones para la estructura del árbol. Estos son particularmente importantes porque la estructura del árbol es realmente irregular: quiero poder decir 'dame los hijos de este nodo' en cualquier nodo: las hojas son solo nodos sin hijos, no algún tipo de cosa especial.
(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)
'()))
Ahora algunas abstracciones para la agenda. Las agendas se representan como listas, pero nadie más lo sabe, por supuesto, y una implementación con más fuerza industrial podría no querer representarlas así.
(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))
Ahora es fácil escribir una versión puramente iterativa de la función (la agenda es mantener la pila), sin todo tipo de construcciones de control complicadas.
(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))))])))
Algo para pensar: ¿qué sucede si reemplaza agenda-prependpor agenda-appenden la función anterior?
He arreglado mi implementación. Si sabe cómo mejorar esto, o sabe cómo implementar subtreesin usar el estilo de continuación de pase (CPS), publique una respuesta. Estoy particularmente interesado en ver una implementación sin CPS (y sin llamada / cc).
Usando el estilo de continuación de pases:
(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))))
Uso:
(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
Un enfoque, que recorre el árbol de forma recursiva, con un contador que rastrea el número actual de nodos visitados. Cada vez que loopse llama antes con el hijo de un nodo, el contador se incrementa, por lo que cuando loopregresa de caminar un subárbol, el contador refleja el número de nodos del árbol visitados hasta el momento (que es donde su lógica está fallando). Utiliza una continuación de "salida" para hacer un cortocircuito y desenrollar la pila de llamadas cuando se encuentra el nodo deseado, devolviéndolo directamente desde lo más profundo de la recursividad.
(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)
Dialecto de esquema de pollo; No tengo Racket instalado. Cualquier conversión necesaria se deja como ejercicio para el lector.
(parece que reemplazar foldcon foldles suficiente)
Bien, veamos ... La estructura general de tales enumeraciones de profundidad primero es con una pila mantenida explícitamente (o para el orden de amplitud primero, una cola):
(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))))))
Esto hace algo similar pero no exactamente lo que querías:
> (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)))
Según su ejemplo, desea omitir el primer elemento en las aplicaciones:
(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))))))
para que ahora, como querías,
> (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)))