Transversal de árbol de posdatos con clojure.zip para editar nodos

Question

Tengo un árbol representado como un vector anidado. Quiero tener una generalización de indexed para los árboles, que muestra el índice de cada nodo de este tipo,

(visit 42); => [0 42] 
(visit [6 7]); => [0 
       ;  [[0 6] 
       ;  [1 7]]] 

La aplicación ingenua usaría clojure.zip directamente (as already asked here)

(defn visit [tree] 
    (loop [loc (vector-zip tree)] 
    (if (end? loc) 
     (root loc) 
     (recur 
     (next (edit loC#(conj 
          [(count (lefts loc))] 
          %))))))) 

Pero recurrentes con clojure.zip/next realiza un recorrido de preorden, resultando en un bucle infinito en este caso (los nodos no visitados obtienen conj ed en un vector [:found] infinitamente). Otro enfoque sería usar clojure.walk/postwalk, pero no proporciona información estructural, como índice.

¿Cómo implementarías esto? ¿Hay un postorder-next para zip que pueda resolverlo de inmediato?

Answer 1

No estoy seguro de si entiendo lo que estás tratando de hacer, pero los ejemplos me sugieren que los índices asignados a los nodos corresponden al número de sus hermanos de la izquierda (ya que en el segundo ejemplo tanto la raíz nodo y el hijo 6 están etiquetados con 0). Actualización: Aparentemente simplemente leí mal el ejemplo visit la primera vez, hace que la intención sea lo suficientemente clara ... Afortunadamente, ahora que lo leí correctamente, me parece que la respuesta a continuación es correcta.

Si eso es correcto, esta es una solución basada en clojure.walk/postwalk:

(defn index-vec-tree [vt] 
    [0 (walk/postwalk 
     (fn [node] 
     (if-not (vector? node) 
      node 
      (vec (map-indexed vector node)))) 
     vt)]) 

Con los ejemplos dados:

user> (index-vec-tree [6 7]) 
[0 [[0 6] [1 7]]] 
user> (index-vec-tree 42) 
[0 42] 

Actualización: Una solución simple usando map-indexed (disponible en 1,2 ; use map + clojure.contrib.seq-utils/indexed en 1.1):

(defn index-vec-tree [vt] 
    (letfn [(iter [i vt] [i (if (vector? vt) 
           (vec (map-indexed iter vt)) 
           vt)])] 
    (iter 0 vt)))