From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 3F2E27EF5E for ; Thu, 14 Jul 2016 21:08:09 +0200 (CEST) IronPort-PHdr: 9a23:NqFZFxAAqEfoTWcT1Bg3UyQJP3N1i/DPJgcQr6AfoPdwSP/7pcbcNUDSrc9gkEXOFd2CrakV06yK6eu5AD1IyK3CmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TWM5DIfUi/yKRBybrysXNWD14LrjavrosybSj4LrQL1Wal1IhSyoFeZnegtqqwmFJwMzADUqGBDYeVcyDAgD1uSmxHh+pX4p8Y7oGxmgO8678NLTYn9eq05S/QYUGVnYCgJ45jAtQPCVheI/nsrcvsZnwAAVwPF9hDhQpDpsm36sedy1TOyIdCzR70uXTWkqatmHkzGkiACYhw063nakIRUi79au1qIoRBy2ZXZZsnBNvdlZq7HO9cdWGtaGM9XWyFbGY66R4QKBusFe+1fqt+u9BM1sRKiCFz0V6vUwThSiyqqjKA= Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=jesper.louis.andersen@gmail.com; spf=Pass smtp.mailfrom=jesper.louis.andersen@gmail.com; spf=None smtp.helo=postmaster@mail-lf0-f50.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jesper.louis.andersen@gmail.com) identity=pra; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jesper.louis.andersen@gmail.com"; x-sender="jesper.louis.andersen@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of jesper.louis.andersen@gmail.com designates 209.85.215.50 as permitted sender) identity=mailfrom; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jesper.louis.andersen@gmail.com"; x-sender="jesper.louis.andersen@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-lf0-f50.google.com) identity=helo; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="jesper.louis.andersen@gmail.com"; x-sender="postmaster@mail-lf0-f50.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CBAADo4odXhjLXVdFchBR8BqcuhX6GNoZ/IoV3AoEsBzsRAQEBAQEBAQERAQEBCAsLCSEvgjIEA4IkAQQBEhEdARsSCwEDAQsGBQsaHQICIgERAQUBChIGExIQh3MBAw8IDqUQgTE+MYs7gWqCWgWFCgoZJwMKUoM9AQEBAQEBAQMBAQEBAQEBGAIGEIlkgQOEbYJUgloFhlQMkj+GEoJ7hUyCOYx4gmuLbxIegQ8PJYI6gVk6ModuAQEB X-IPAS-Result: A0CBAADo4odXhjLXVdFchBR8BqcuhX6GNoZ/IoV3AoEsBzsRAQEBAQEBAQERAQEBCAsLCSEvgjIEA4IkAQQBEhEdARsSCwEDAQsGBQsaHQICIgERAQUBChIGExIQh3MBAw8IDqUQgTE+MYs7gWqCWgWFCgoZJwMKUoM9AQEBAQEBAQMBAQEBAQEBGAIGEIlkgQOEbYJUgloFhlQMkj+GEoJ7hUyCOYx4gmuLbxIegQ8PJYI6gVk6ModuAQEB X-IronPort-AV: E=Sophos;i="5.28,364,1464645600"; d="scan'208,217";a="184858130" Received: from mail-lf0-f50.google.com ([209.85.215.50]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 14 Jul 2016 21:08:03 +0200 Received: by mail-lf0-f50.google.com with SMTP id q132so71416798lfe.3 for ; Thu, 14 Jul 2016 12:08:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=QGBvs3avFIVKA3ddGUqXL7js+0FC/ZvGXQFoE2oNG18=; b=kDOhtGrm98tek0bTzc2WhXlx55D9ga/gqET/UTym5nbKJqi+qJUq038l9g8aeu1s// 29uVXD0nELvDKpyj/TpeMPDGaJ3/ywK81GmAkdSeTAUMXY3mWNzO8KSo41XpOnrquZHe vW6pQhCN0dZJGr/lwe5F8srnUUKK7XdtRrqlUoHrIONtfY3uaOcJ3dUh7EUMn6hGOk/5 upNH6T6YZvqln2qTX/gK8vRegwLVJBX1SjfpMGY+PC4iftnZldhgcX2X9u/0Y+qaYvob uf34ULdh/ynAAl7ab9YwuzLyzTenPFjAOLk8fWgVLVGfkLBSxluixwUHPdnLf0kVk6LW /biw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=QGBvs3avFIVKA3ddGUqXL7js+0FC/ZvGXQFoE2oNG18=; b=Suol4MEtCijrIFoi3Wg79iV1iJrg9mLA8cr4yiVHeXQ5C+fvu022J5BsnvOceP7jYv FOjatMq3FO7Q3Z1CC9N/jnHMK57JtIUC0GYx/Q4Ok/uHepYqdwkMHgLwh2SJgmGFrdos sG/RXeZ7dtf72tmFTFqb5Un1Ek2fuXu6uoGialA/eZZMcfEtiMXUMNrZ/gd5qVuSKhBW 9eVQLLpOvCCQ0kdLKwG72NajwOYPr+PBdoeRXO1FFY47iKcJwceo7BwL3SfTgpOukLb6 SxC/7/XhGF0T6tYz88a6M7a0jVDZOCTxc7fVXyhfG92qHKA4os+5NB7CqaVdd2/BAzR4 ausg== X-Gm-Message-State: ALyK8tJ2OM3rmNy/HawuHsenTsG5HIT+ryfrWoGmIDy7h3KJ5YCPhWG6DCFAgYmkeBYqKLl3LVmHo8aZJS+xRw== X-Received: by 10.46.1.35 with SMTP id 35mr7381085ljb.8.1468523282782; Thu, 14 Jul 2016 12:08:02 -0700 (PDT) MIME-Version: 1.0 Received: by 10.25.21.168 with HTTP; Thu, 14 Jul 2016 12:07:23 -0700 (PDT) In-Reply-To: References: <2a4393e2-eea1-1876-f29a-188ed992e5b4@tu-berlin.de> From: Jesper Louis Andersen Date: Thu, 14 Jul 2016 21:07:23 +0200 Message-ID: To: =?UTF-8?Q?Christoph_H=C3=B6ger?= Cc: caml users Content-Type: multipart/alternative; boundary=001a1142bf329d61da05379d388e Subject: Re: [Caml-list] Map that maintains insertion-order on keys --001a1142bf329d61da05379d388e Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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=C3=B6ger < 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))))) =3D!=3D [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=C3=B6ger > > Technische Universit=C3=A4t Berlin > Fakult=C3=A4t IV - Elektrotechnik und Informatik > =C3=9Cbersetzerbau 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 > --=20 J. --001a1142bf329d61da05379d388e Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Perhaps this can be built out of smaller data structures.<= div>
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) a= nd 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 M= ap from Core. The idea is that the map values are elements of the doubly li= nked 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 jus= t 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 tha= t to people who write OCaml on a daily basis :)

If= you *do* need persistence, one way is to keep two maps. One maps a sequenc= e 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 P= M, Christoph H=C3=B6ger <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 whi= ch 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.<= br>
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))))) =3D!=3D [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=C3=B6ger

Technische Universit=C3=A4t Berlin
Fakult=C3=A4t IV - Elektrotechnik und Informatik
=C3=9Cbersetzerbau und Programmiersprachen

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

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

--
Caml-list mailing list.=C2=A0 Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocam= l_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs



--
=
J.
--001a1142bf329d61da05379d388e--