Обход дерева по порядку с помощью clojure.zip для редактирования узлов - PullRequest
Новая
       20

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

5 голосов
/ 30 июля 2010

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

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

Наивная реализация будет использовать clojure.zip напрямую (, как уже было сказано здесь ) 

(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 преобразуются в вектор [:found] бесконечно). Другой подход мог бы использовать clojure.walk/postwalk, но он не предоставляет структурную информацию, такую ​​как индекс.

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

1 Ответ

4 голосов
/ 30 июля 2010

Я не уверен, что понимаю, что вы пытаетесь сделать, но примеры подсказывают мне, что индексы, присвоенные узлам, соответствуют количеству их левых братьев и сестер (поскольку во втором примере оба корневых узлаи 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)))
...