Doubly linked data structures in erlang

Question

Hi I want to make a tree that keeps two-way references between parent and children. But it seems impossible to achive since when I create first object I do not have the other one yet therefore cannot have a reference to it. Here is some sample code.

-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.

Another example to this problem would be implementing a doubly linked list (http://en.wikipedia.org/wiki/Doubly_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.

Is there a way to implement this kind of structure.

Answer 1

You can make doubly linked lists when you have "links" (like pointers). In erlang you don't have such links and you don't have even real variables, you can't change them. Here are some examples for circular lists, but they should be implemented with caution: Can Circular Lists be defined in Erlang?

Maybe you could tell us why you need doubly linked tree? Maybe there is a better solution in erlang.

Edit: You could use digraph. Your tree can be represented as cyclic graph where you have vertices from A to B and from B to A. Example of a tree with root node A and children B and 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).

Result: ["vertexB","vertexA","vertexC"]

Answer 2

You could inspect how this implemented in ferd's zippers library