Traversal dell'albero postale con clojure.zip per modificare i nodi

Question

Ho un albero rappresentato come vettore annidato. Voglio avere una generalizzazione indexed per alberi, mostrando l'indice di ogni nodo simili,

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

L'attuazione naive userebbe clojure.zip direttamente (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))] 
          %))))))) 

Ma ripetono clojure.zip/next esegue un attraversamento preordinato, creando un loop infinito in questo caso (i nodi non visitati ricevono conj in un vettore infinitamente [:found]). Un altro approccio sarebbe utilizzare clojure.walk/postwalk, ma non fornisce informazioni strutturali, come l'indice.

Come implementeresti questo? C'è uno postorder-next per zip che lo risolverebbe subito?

Answer 1

Non sono sicuro di capire cosa stai cercando di fare, ma gli esempi mi suggeriscono che gli indici assegnati ai nodi corrispondono al numero dei loro fratelli di sinistra (poiché nel secondo esempio sia la radice nodo e il figlio 6 sono etichettati con 0). Aggiornamento : Apparentemente ho semplicemente interpretato erroneamente l'esempio visit la prima volta - rende l'intenzione abbastanza chiara ... Fortunatamente ora che l'ho letto correttamente mi sembra che la risposta qui sotto sia corretta.

Se questo è corretto, questa è una soluzione basata su 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 gli esempi riportati:

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

Aggiornamento: Una soluzione semplice utilizzando map-indexed (disponibile in 1.2 ; utilizzare map + clojure.contrib.seq-utils/indexed in 1.1):

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