Перемещение дерева заказов с помощью clojure.zip для редактирования узлов

Question

У меня есть дерево, представленное как вложенный вектор. Я хочу иметь обобщение indexed для деревьев, с указанием индекса каждого узла, как это,

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

Наивный реализация будет использовать clojure.zip непосредственно (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))] 
          %))))))) 

Но повторяющиеся с clojure.zip/next выполняет обход предзаказов, в результате чего в этом случае возникает бесконечный цикл (независящие узлы получают conj ed в вектор [:found] бесконечно). Другим подходом будет использование clojure.walk/postwalk, но он не содержит структурной информации, такой как индекс.

Как вы это реализуете? Есть ли postorder-next для zip, который бы сразу решил его решить?

Answer 1

Я не уверен, понимаю ли я, что вы пытаетесь сделать, но примеры подсказывают мне, что индексы, назначенные узлам, соответствуют числу их левых братьев и сестер (так как во втором примере как корень узел и дочерний элемент 6 помечены 0). Обновление: По-видимому, я просто неправильно читал пример visit в первый раз - он делает намерение достаточно ясным ... К счастью, теперь, когда я прочитал его правильно, мне кажется, что ответ ниже правильный.

Если это верно, то это clojure.walk/postwalk основанное решение:

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

С приведенными примерами:

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

Обновление: Простое решение с помощью map-indexed (доступен в 1.2 , использование map + clojure.contrib.seq-utils/indexed в 1.1):

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