[Caml-list] Map that maintains insertion-order on keys

[Caml-list] Map that maintains insertion-order on keys

[Christoph Höger]

Dear all,

I need a data structure has all the functionality of a Map.t but also
gives keys in the order of insertion. Is such a structure readily
available in some OCaml library?

thanks,

Christoph
-- 
Christoph Höger

Technische Universität Berlin
Fakultät IV - Elektrotechnik und Informatik
Übersetzerbau und Programmiersprachen

Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin

Tel.: +49 (30) 314-24890
E-Mail: christoph.hoeger@tu-berlin.de

Re: [Caml-list] Map that maintains insertion-order on keys

[Jesper Louis Andersen]

[-- Attachment #1: Type: text/plain, Size: 1078 bytes --]

Hi,

Could you give some small example of what you want or a more precise
definition? I can think of at least 3 ways to parse meaning out of "gives
keys in order of insertion", and I don't know which you might want.

On Thu, Jul 14, 2016 at 8:02 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:

> Dear all,
>
> I need a data structure has all the functionality of a Map.t but also
> gives keys in the order of insertion. Is such a structure readily
> available in some OCaml library?
>
> thanks,
>
> Christoph
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
J.

[-- Attachment #2: Type: text/html, Size: 2008 bytes --]

Re: [Caml-list] Map that maintains insertion-order on keys

[Christoph Höger]

Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> Hi,
> 
> Could you give some small example of what you want or a more precise
> definition? I can think of at least 3 ways to parse meaning out of
> "gives keys in order of insertion", and I don't know which you might want.

What I mean is that a map that is created by consecutive Map.add
applications, yields the keys in the order of the add() applications, i.e.

Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]

it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
much.





-- 
Christoph Höger

Technische Universität Berlin
Fakultät IV - Elektrotechnik und Informatik
Übersetzerbau und Programmiersprachen

Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin

Tel.: +49 (30) 314-24890
E-Mail: christoph.hoeger@tu-berlin.de

Re: [Caml-list] Map that maintains insertion-order on keys

[Jesper Louis Andersen]

[-- Attachment #1: Type: text/plain, Size: 2600 bytes --]

Perhaps this can be built out of smaller data structures.

Clearly the representation [k1, v1; k2, v2; ...; kn, vn] is a map with the
property, but most operations are in the order of O(n) and thus wholly
unsatisfactory for any map with more than, say, 500 elements.

If you don't need persistence, my intuition would be to use Janes St. Core
and then build it out of Doubly_linked and Map from Core. The idea is that
the map values are elements of the doubly linked list, we wrap Map and
maintain the DL list as well. Then the insertion order can be handled by
the DL list, so asking for the ordered keys is just walking the list in the
direction desired. This keeps the asymptotics of the Map since operations
on the DL list are O(1).

There might be a direct implementation of this idea, but I'll defer that to
people who write OCaml on a daily basis :)

If you *do* need persistence, one way is to keep two maps. One maps a
sequence number to a key. The other maps a key to a pair of a sequence
number and a value. The triple of (sequence_no, order_map, map) should be
persistenly maintainable, under the price of a factor 2 efficiency loss.

Better (functional) data structures may exist for this problem, but I don't
know about them from memory alone.

On Thu, Jul 14, 2016 at 8:44 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:

> Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> > Hi,
> >
> > Could you give some small example of what you want or a more precise
> > definition? I can think of at least 3 ways to parse meaning out of
> > "gives keys in order of insertion", and I don't know which you might
> want.
>
> What I mean is that a map that is created by consecutive Map.add
> applications, yields the keys in the order of the add() applications, i.e.
>
> Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
> k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]
>
> it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
> much.
>
>
>
>
>
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
J.

[-- Attachment #2: Type: text/html, Size: 3671 bytes --]

Re: [Caml-list] Map that maintains insertion-order on keys

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 1762 bytes --]

You could use a pair of:
- a map and
- a list of weak pointers to keys with a count of present items and deleted
items (you would compact the list whenever there are more deleted items
than present items)

Why the counts: removing items from the list on deletion is too slow.
Why the weak pointers: using keys directly could increase their lifetime
after they have been deleted from the map.
If you don't need deletion, just a list of keys is fine.

On Thu, Jul 14, 2016 at 2:44 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:

> Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> > Hi,
> >
> > Could you give some small example of what you want or a more precise
> > definition? I can think of at least 3 ways to parse meaning out of
> > "gives keys in order of insertion", and I don't know which you might
> want.
>
> What I mean is that a map that is created by consecutive Map.add
> applications, yields the keys in the order of the add() applications, i.e.
>
> Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
> k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]
>
> it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
> much.
>
>
>
>
>
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2647 bytes --]