[erlang-questions] Tuples referencing each other problem

[Grzegorz Junka]

Zipper looks interesting but I don't think it would suit here. Keeping 
paths to leafs could work but since the tree is dynamic those paths 
would often change and it would be very difficult to update paths that 
have already been stored.

In short, I have keys, which may be any Erlang terms, and numerical Ids 
assigned to those terms. Keys must be sorted. Numerical Ids are 
increasing monotonically. Then the following lookups should be efficient:

1. Having a key quickly search for its numeric Id
2. Having a numeric Id quickly get back the key

Also the following conditions should be met:

3. The same key should be always assigned the same numeric Id
4. One key has always one numeric Id (and vice versa), so they are 
always added or removed together

Since keys can be of any length I don't want to store them more than 
once. And since they must be sorted I was thinking about using a B+Tree. 
Then another structure to map the numeric Id back to their keys.

An obvious solution would be to make the B+Tree bidirectional - the key 
would be recreated by traversing the tree back from a leaf to the root. 
The other structure would then need to keep a mapping between the 
numeric Id and the reference to the leaf for the key corresponding to 
that numeric Id.

But an equally valid solution would be to tag all nodes of the B+Tree 
with numbers and store tags to parents in their children. Then in 
another structure, e.g. an array, the mapping between the tag and its 
node. That would also allow to traverse the tree backward from leafs to 
the root.

GrzegorzJ


On 22/09/2017 00:37, Richard A. O'Keefe wrote:
>
>
> On 22/09/17 2:23 AM, Grzegorz Junka wrote:
>> To answer your question Richard, I don't actually need a cyclical
>> structure. As I mentioned, this is a simplification of a more specific
>> problem. I didn't want to describe all the specifics to ask a question.
>> I need to design a tree, a variant of a HAMT tree, but which can be
>> traversed in both directions, from the root to leafs and from leafs to
>> the root (independently, i.e. starting from a reference to a leaf rather
>> than recursively).
>
> Of course this pushes back the question a further step.
> Why do you want to traverse the tree in both directions?
>
> Might the "zipper" approach be any use?
>
> If you want references to leaves, such references could be paths.
> I used that technique once in a programming language that used
> reference counting, so that link cycles meant no collection.
> (Yes, I know modern reference-based collectors have solved that
> problem.)  I've also used that technique for processing XML in
> a pure functional language.
>
> In an imperative context, that doesn't work very well because the
> tree structure might change.  The DOM suffers from trying to make
> this "work" in some sense, but trying to iterate over a graph
> while something else is changing it is never going to be easy.
>
> It is possible that the Haskell "Functional Graph Library"
> may be relevant to your needs.
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions