Clojure zipper функция пути не завершена?

Question

РЕДАКТИРОВАТЬ # 2: Весь этот вопрос и исследование были основаны на моем отсутствующем фундаментальном понятии молнии; что они представляют собой перспективу в структуре данных с точки зрения конкретного узла. Таким образом, застежка-молния всегда - пара текущего узла, а остальная часть дерева выглядит с точки зрения этого узла. Сначала я пытался создать целую новую структуру с застежкой-молнией, а сама молния была всем, что мне нужно, все время. Я оставлю все это для потомков, в надежде, что кому-то это поможет (или это служит предупреждением для любых преемников!).

Оригинальный вопрос:

Я пытаюсь получить мою голову вокруг с помощью застежки-молнии, чтобы манипулировать деревьев. Конкретная проблема заключается в том, что мне нужно генерировать на маршрутах времени выполнения между двумя узлами, которые соответствуют произвольным критериям в произвольном дереве.

Я думал, что могу использовать функцию path, чтобы получить маршрут до места, позвонив по телефону path в текущее местоположение. Но возвращаемый путь, кажется, опускает последний шаг (ы), необходимые для его прохождения.

Например:

(def test-zip (vector-zip [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]])) 
(-> test-zip 
    down right right down 
    right down right right 
    node) 

дает 5, но

(-> test-zip 
    down right right down 
    right down right right 
    path) 

дает

[[0 [1] [2 [3 [4] 5 [6 [7] [8]]]]] [2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]]] 

, который не является тем же место (это отсутствует эффект последних трех шагов , down right right).

Похоже, что функция пути только доставит вас в родительское расположение в дереве, игнорируя любые братья и сестры между вами и фактическим местоположением.

Я пропустил пункт path функции? Я предположил, что, учитывая дерево и путь, применение пути к дереву приведет вас к исходному расположению пути, а не отчасти там.

UPDATE: Я использовал следующее определение функции для компиляции пути узлов от начального местоположения до конечного местоположения:

(defn lca-path [start-loc end-loc] 
    (let [sczip (z/root start-loc) 
     start-path (z/path start-loc) 
     start-node (z/node start-loc) 
     end-path (z/path end-loc) 
     end-node (z/node end-loc) 
     lca-path (filter (set start-path) end-path) 
     lca-node [(last lca-path)] 
     lca-to-start (conj (vec (drop (count lca-path) start-path)) start-node) 
     lca-to-end (conj (vec (drop (count lca-path) end-path)) end-node) 
     ] 

    (concat (reverse lca-to-start) lca-node lca-to-end)) 
) 

Довольно сильно влияет общение с @Mark Фишер, спасибо !

Answer 1

Я думаю, что вы правы, это родительский путь, и это подтверждается. at this site, path возвращает «все поддеревья от корня дерева до чуть выше текущего loc».

Для вашей структуры, дерево:

A 
/| \ 
0 o B 
    |/\ 
    1 2 C __ 
     /|\ \ 
     3 o 5 o 
     | /|\ 
     4 6 o o 
      | | 
      7 8 

Таким образом, 3 узлов обозначены А, В, С являются родительскими узлами какие приводит к родителю 5, которые являются:

A: [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]] 
B: [2 [3 [4] 5 [6 [7] [8]]]] 
C: [3 [4] 5 [6 [7] [8]]] 

, который является результатом, который вы получаете.

EDIT: Я создал эту функцию для поиска между двумя значениями в векторе и возврата между ними path. Помогает ли это? Я не специалист по застежкам-молнией, так что это учится и для меня.

(defn between [v s e] 
    (let [zv (zip/vector-zip v) 
     find-loc (fn [zv l] 
        (loop [loc zv] 
        (if (= l (zip/node loc)) 
         loc 
         (if (zip/end? loc) 
          nil 
          (recur (zip/next loc)))))) 
     sv (zip/vector-zip (-> (find-loc zv s) zip/up zip/node)) 
     e-in-sv (find-loc sv e) 
     path-s-e (when (some? e-in-sv) 
        (zip/path e-in-sv))] 
    path-s-e)) 

Она находит путь между родителем начального значения и родителя конечного значения, и вы можете использовать его как:

(def sov [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]) 
(between sov 2 6) 
=> [[2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]] [6 [7] [8]]] 

Я хожу по дереву, чтобы найти родителей из начальное значение, а затем создайте новую молнию из своего родителя, чтобы путь был ограничен от начальной точки. Вспомогательная функция «find-loc» возвращает застежку-молнию для записи, которую вы ищете, например. «5» внутри вектора. sv - это родительский вектор, содержащий начальное значение.

Если нет пути, он возвращает нуль, например. между 1 и 4 вам придется пройти по 2 элементам.

Это было в ответ на ваши комментарии о необходимости найти значение в конечном узле (например, 5 в [3 [4] 5 [6 [7] [8]]]), что я не думаю, что вам нужно делать, но без реального примера того, что вы делаете сложно комментировать.

Кстати, в векторе могут быть гораздо лучшие способы перемещения/нахождения значений, чем пользовательская функция, но, как я уже сказал, молнии для меня тоже новы.