Двойно связанные структуры данных в erlang

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

-record(node,{name,children,root}).

main()->
    A = #node{name="node-A",
          children=[B], %variable B is  unbound
          root=nil},
    B = #node{name="node-B",
          children=[],
          root=A},
    Tree = A.

Другим примером этой проблемы может быть реализация двусвязного списка (http://en.wikipedia.org/wiki/Double_linked_list).

-record(node,{prev,name,next}).

main()->
    A = #node{prev=nil,
          name="node-A",
          next=B}, % variable B is unbound
    B = #node{prev=A,
          name="node-B",
          next=nil},
    LinkedList = A.

Есть ли способ реализовать такую ​​​​структуру.


tree erlang
person yilmazhuseyin    schedule 15.12.2012    source источник
comment
Почему бы не определить вашу структуру в -define, где дочерний элемент по умолчанию имеет значение undefined. Затем, после создания узла B, создайте NodeA = B#node{children=A}.... Извините, что это не работает. Хотел бы я знать, как удалять заметки   -  person Jr0    schedule 16.12.2012
comment
почему бы не попробовать сначала создать детей, а затем назначить им родителей? ИЛИ создать родителей и дать им дочерние элементы по умолчанию, а затем, как только дети будут готовы, обновить родителей?   -  person Muzaaya Joshua    schedule 17.12.2012

Ответы (5)


arrow_upward
3
arrow_downward

Вы можете создавать двусвязные списки, когда у вас есть «ссылки» (например, указатели). В эрланге у вас нет таких ссылок и у вас нет даже реальных переменных, вы не можете их изменить. Вот несколько примеров циклических списков, но их следует применять с осторожностью: Can Circular Списки будут определены в Erlang?

Может быть, вы могли бы рассказать нам, зачем вам нужно двусвязное дерево? Возможно, в erlang есть лучшее решение.

Изменить: вы можете использовать digraph. Ваше дерево может быть представлено в виде циклического графа, в котором у вас есть вершины от A до B и от B до A. Пример дерева с корневым узлом A и дочерними элементами B и C:

main()->
    Tree = digraph:new([cyclic]),
    A = digraph:add_vertex(Tree,"vertexA"),
    B = digraph:add_vertex(Tree,"vertexB"),
    C = digraph:add_vertex(Tree,"vertexC"),
    digraph:add_edge(Tree, A, B),
    digraph:add_edge(Tree, B, A),
    digraph:add_edge(Tree, A, C),
    digraph:add_edge(Tree, C, A),
    digraph:get_path(Tree, B, C).

Результат: ["vertexB","vertexA","vertexC"]

person yetihehe    schedule 15.12.2012
comment
Есть ли способ отслеживать/сохранять ссылку на конец связанного списка, чтобы выполнять операции добавления O (1) в erlang? - person CMCDragonkai; 17.10.2014
comment
Нет, вы не можете добавить в конец списка. Однако вы можете смоделировать это на моем примере. Digraph использует ets со стоимостью вставки O(1). - person yetihehe; 15.12.2014

arrow_upward
3
arrow_downward

Вы можете посмотреть, как это реализовано в библиотеке zippers от ferd.

person danechkin    schedule 16.12.2012
comment
О, это аккуратно. Рад, что нашел это :). - person l04m33; 21.12.2012

arrow_upward
3
arrow_downward

Вы можете определить запись как

-record(my_node,{левый дочерний,правый дочерний,родительский,значение}.

и сохраните свое дерево в таблице ets,

ets:new(my_tree,[named_table, ordered_set, public]),
...

а затем вы можете управлять ссылкой, используя ключ таблицы как «указатель»

Root = {make_ref(),#my_node{value=somevalue}}
ets:insert(my_tree,Root),
A_child = {make_ref(),#my_node{value=othervalue}},
addchild(Root,A_child,left),
...

addchild(Parent={Pref,Pval},Child={Cref,Cval},left) ->
    ets:insert(my_tree,{Pref,Pval#my_node{leftchild=Cref}}),
    ets:insert(my_tree,{Cref,Cval#my_node{parent=Pref}});
addchild(Parent={Pref,Pval},Child={Cref,Cval},right) ->
    ets:insert(my_tree,{Pref,Pval#my_node{rightchild=Cref}}),
    ets:insert(my_tree,{Cref,Cval#my_node{parent=Pref}}).

Но, возможно, вам следует взглянуть на представление данных в стиле erlang, чтобы решить вашу проблему. Существует также проблема с решением, которое я предлагаю, если к дереву обращаются несколько процессов, потому что обновление дерева не является атомарным. В этом случае вы должны использовать mnesia, уровень базы данных над ets, который принесет вам атомарную транзакцию.

person Pascal    schedule 16.12.2012

arrow_upward
3
arrow_downward

Нет, прямого способа реализации двусвязных списков в Erlang нет, так как все данные неизменяемы. И даже если бы вы могли настроить его (чего вы не можете), вы не могли бы сделать что-либо со всеми неизменяемыми данными. Другие решения, представленные здесь, показывают способы обойти это путем создания структур данных, которые ведут себя как двусвязные списки. Но нет.

person rvirding    schedule 17.12.2012

arrow_upward
2
arrow_downward

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

A = #node{name="node-A",
      children=["node-B"],
      parent=nil},
B = #node{name="node-B",
      children=[],
      parent="node-A"},
NodeDict = dict:from_list([{A#node.name, A}, {B#node.name, B}]),
Tree = #tree{root=A#node.name, nodes=NodeDict}.
person Alexey Romanov    schedule 16.12.2012