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

[Jesper Louis Andersen <jesper.louis.andersen@gmail.com>]

[-- 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 --]