[erlang-questions] Tuples referencing each other problem

Grzegorz Junka <>
Mon Sep 25 08:35:43 CEST 2017


Fair enough, I missed that you can set ordered_set in ETS, but 
nevertheless it won't work with maps. However, even if I use ETS the Key 
is still stored twice, isn't? (once as the key for ordered_set, once as 
the value when the Id is the key).


On 24/09/2017 16:43, Jesper Louis Andersen wrote:
> Of course it will work: the ETS table is an ordered_set. This ensures 
> that you have Term order. Now, in Erlang, numbers and thus integers 
> have order less than everything else. In short, min/1 is given by a 
> call to ets:first/1. To get max, we observe that the atom 'x' is not 
> part of your keys, nor part of the integers. So it is larger than any 
> integer. If we ask ets:prev/2 on that 'x', we get max/1.
>
> This covers the range operations on IDs. For the range operations on 
> keys, it is even easier because they already have sorted order. You 
> can also get rather fast traversal by using ets:select/1,2 and using 
> the continuations to walk the data set in larger chunks.
>
> On Sun, Sep 24, 2017 at 6:02 PM Grzegorz Junka < 
> <mailto:>> wrote:
>
>     Thanks but that won't work. As mentioned keys must be sorted so
>     that I can quickly query for range from min/max key. I could add
>     an index but in that case the key would be stored twice, once in
>     the index and once in the value, which I wanted to avoid.
>
>     GrzegorzJ
>
>
>     On 24/09/2017 15:29, Jesper Louis Andersen wrote:
>>     Consider an ETS table and insert
>>
>>     [{Key, Id}, {Id, Key}]
>>
>>     This ensures fast lookup in both directions. Alternatively, run
>>     this in a map. I often do this when mapping monitor references in
>>     code.
>>
>>     On Sat, Sep 23, 2017 at 3:50 PM Grzegorz Junka <
>>     <mailto:>> wrote:
>>
>>         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
>>         > 
>>         <mailto:>
>>         > http://erlang.org/mailman/listinfo/erlang-questions
>>
>>         _______________________________________________
>>         erlang-questions mailing list
>>          <mailto:>
>>         http://erlang.org/mailman/listinfo/erlang-questions
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20170925/bc6d2c3d/attachment.html>


More information about the erlang-questions mailing list