[erlang-questions] Tuples referencing each other problem
Sat Sep 23 15:50:30 CEST 2017
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
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
More information about the erlang-questions