«переизбыточная» чисто функциональная структура данных дерева

Question

Недавно я приобрел Inferring Phylogenies Джозефом Фелсенштейном, который представляет собой отличную книгу о математических и вычислительных методах для вывода филогенетических деревьев и играл с реализацией некоторых алгоритмов, которые он описывает.

В частности, я заинтересован в том, чтобы использовать это в функциональной настройке с постоянными структурами данных, так как многие методы включают в себя прохождение через пространство возможных деревьев, и было бы неплохо дешево запомнить историю того, (по сравнению с «мирами» в this blog post), легко кэшировать ранее вычисленные значения для поддеревьев и т. д.

Проблема заключается в том, что многие методы включают в себя «переучивание» деревьев, который я не могу понять, как делать дешево чисто функциональным способом. В основном я нужен способ захвата идеи, что каждый из следующих (с использованием Clojure обозначений, представляющие дерева как векторы):

[:a [:b [:c :d]]] 
[:b [:a [:c :d]]] 
[:a [:b [:d :c]]] 
[:b [:a [:d :c]]] 
[[:a :b] [:c :d]] 
[[:c :d] [:a :b]] 
[:c [:d [:a :b]]] 
[:d [:c [:a :b]]] 
[:c [:d [:b :a]]] 
[:d [:c [:b :a]]] 

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

a b 
\/
    | 
/\ 
c d 

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

В книге Felsenstein описывает структуру данных для дешевки rerootable дерева, которое выглядит примерно следующая поспешно сделали диаграмму

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

Я чувствую, что должен быть способ сделать то, что я хочу, используя молнии, но я играл с clojure.core/zip на некоторое время и никуда не уходил.

Кто-нибудь знает о реализации чего-то подобного или имеет предложения по вещам, которые я должен прочитать/документы, которые я должен посмотреть/идеи о том, как это сделать?

Спасибо!

Answer 1

некорневого дерево представляет собой график, со следующими характеристиками:

• Это является симметричным/неориентированным - это его собственным обратным.
• Это сильно связано - вы можете получить везде откуда угодно.
• Единственный способ вернуться к тому, откуда вы пришли, - это восстановить ваши шаги .

Стандартный способ представления графика - это карта, предоставляющая набор соседей для каждого узла. Это то, что делает the standard clojure graph library, хотя его операции скрыты за избыточным defstruct.

Для примера, карта

{:I #{:a :b :c :d}, :a #{:I}, :b #{:I}, :C#{:I}, :d #{:I}} 

Это неориентированный граф когда его собственный inverse, где

(defn inverse [g] 
    (apply merge-with clojure.set/union 
     (for [[x xs] g, y xs] {y #{x}}))) 

Вам не нужно ничего делать, чтобы корень это где угодно. Как говорит @noisesmith, корень - это только тот узел, с которого вы начинаете перечислять. Судя по диаграмме, это в равной степени относится к структуре данных Фельзенштейна.

Если, как показывает диаграмма, только ваши внутренние узлы являются многосвязными, вы можете сэкономить некоторое пространство, сопоставляя непосредственно с каждого внешнего узла его уникальному соседу. Ваш пример станет

{:I #{:a :b :c :d}, :a :I, :b :I, :c :I, :d :I} 

, возможно, лучше выражены в виде двух карт:

{:internals {:I #{:a :b :c :d}}, :externals {:a :I, :b :I, :c :I, :d :I}} 

Answer 2

виртуальная машина фактически не дает нам доступ к указателям, как, например, что мы можем непосредственно манипулировать. Но у нас есть несколько вариантов представления двухсвязной структуры.

Это очень похоже на график, а для разреженных графиков это классическое представление - adjacency list. Преимуществом списков смежности является то, что они разыменовываются по имени, а не полагаются на идентификатор указателя/объекта, и поэтому мы можем выражать произвольные круговые или самореляционные пути в структуре без какой-либо необходимости в мутации.

именования узлы в алфавитном порядке слева направо/сверху вниз:

{:a [:c] 
:b [:d] 
:c [:a :d :e] 
:d [:b :c :e] 
:e [:c :d :g] 
:f [:h] 
:g [:e :h :i] 
:h [:f :g :i] 
:i [:g :h]} 

элементы в сети ищутся по имени, и стрелка, выходящая из этого элемента представлены в виде вектора, как связанное значение. Обход может быть реализован как рекурсивная функция, просматривающая узел для перехода на каждую итерацию. «Корень» - это просто элемент, используемый для начала вашего обхода (:i на вашем графике).

Различные виды вставки/расщепления перегруппировки может быть сделано с conj, update-in, assoc и т.д., так как хэш-карта буквального является регулярным Clojure стойкими структуры данных.