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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id C4B5E7FC53 for ; Tue, 29 Sep 2015 15:35:54 +0200 (CEST) IronPort-PHdr: 9a23:Aocx5hXpcHNnoKhWq/RJ3E+MvonV8LGtZVwlr6E/grcLSJyIuqrYZxWHt8tkgFKBZ4jH8fUM07OQ6PC8HzFfqsje+Fk5M7VyFDY9wf0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3CwN5K6zPF5LIiIzvjqbpq8GVPloD2mX1SIgxBSv1hD2ZjtMRj4pmJ/R54TryiVwMRd5rw3h1L0mYhRf265T41pdi9yNNp6BprJYYAu3SNp41Rr1ADTkgL3t9pIiy7UGCHj20+2AEX24Kvh1NCgnDpFGmD9ai+hf948V00jObMMm+drs0VC6v9e8/RxbikiYKM3gi+2HakMFqpK1eqROl4Rd4xtiHTpuSMa9Ff6bae5sxX3dIWMtKH3haA4a7ac0EFfcIO+tD6dOl/wQmqEeuQw62C7W8mXdzmnbq0PhigKwaGgbc0VllQosD Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=Pass smtp.pra=simon.cruanes.2007@m4x.org; spf=Pass smtp.mailfrom=SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org; spf=Pass smtp.helo=postmaster@mx3.polytechnique.org Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of simon.cruanes.2007@m4x.org designates 91.121.62.107 as permitted sender) identity=pra; client-ip=91.121.62.107; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="simon.cruanes.2007@m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org designates 91.121.62.107 as permitted sender) identity=mailfrom; client-ip=91.121.62.107; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of postmaster@mx3.polytechnique.org designates 91.121.62.107 as permitted sender) identity=helo; client-ip=91.121.62.107; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=VFKD=KD=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="postmaster@mx3.polytechnique.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CtAAA5kgpWnGs+eVteg3hpAYMpqSmHYIkvAQ2BfYdDOBQBAQEBAQEBARABAQEBAQgUCU+CHYIHAQEBAwEjBEAHCxALGAkEHQICDwUoCRgTEogHAwoMCbZyjzkDhT8ZilGBBoJugTaDWS+BFAWFfQyPZAeFFod4gVRGlUCDbx8BAYRFb4kfAQEB X-IPAS-Result: A0CtAAA5kgpWnGs+eVteg3hpAYMpqSmHYIkvAQ2BfYdDOBQBAQEBAQEBARABAQEBAQgUCU+CHYIHAQEBAwEjBEAHCxALGAkEHQICDwUoCRgTEogHAwoMCbZyjzkDhT8ZilGBBoJugTaDWS+BFAWFfQyPZAeFFod4gVRGlUCDbx8BAYRFb4kfAQEB X-IronPort-AV: E=Sophos;i="5.17,608,1437429600"; d="asc'?scan'208";a="179972553" Received: from mx3.polytechnique.org ([91.121.62.107]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-GCM-SHA384; 29 Sep 2015 15:35:54 +0200 Received: from carty (unknown [78.250.192.104]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTPSA id 26A4C1E0842; Tue, 29 Sep 2015 15:35:51 +0200 (CEST) Date: Tue, 29 Sep 2015 15:35:37 +0200 From: Simon Cruanes To: Gabriel Scherer Cc: =?utf-8?Q?S=C3=A9bastien?= Hinderer , caml users Message-ID: <20150929133537.GA21028@carty> References: <20150929124344.GA13383@pl-59055.rocqadm.inria.fr> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="u3/rZRmxL6MmkK24" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23.1 (2014-03-12) X-AV-Checked: ClamAV using ClamSMTP at mx3.polytechnique.org (Tue Sep 29 15:35:53 2015 +0200 (CEST)) X-Spam-Flag: No, tests=bogofilter, spamicity=0.000000, queueID=6C5F61E0844 X-Org-Mail: simon.cruanes.2007@polytechnique.org Subject: Re: [Caml-list] polymorphic sets? --u3/rZRmxL6MmkK24 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Le Tue, 29 Sep 2015, Gabriel Scherer a =C3=A9crit : > I don't think this is possible. >=20 > In Batteries, we ported (duplicated) the existing implementation of OCaml= 's > Set and Map modules to give them a "concrete" definition, with no > abstraction and with each function parametrized over a comparison > operation, on top of which both a functorized and a polymorphic interface > are built. You may be interested in the code: >=20 >=20 > https://github.com/ocaml-batteries-team/batteries-included/blob/master/sr= c/batSet.ml >=20 > https://github.com/ocaml-batteries-team/batteries-included/blob/master/sr= c/batMap.ml >=20 > Note that the polymorphic sets (or maps) are less statically-safe than > their functorized counterpart, because they are parametrized over their > comparison function at creation time (a better choice, I think, that > enforcing the use polymorphic comparison, think of records with a function > parameter for example), but then you can mix two sets with same carrier > type but different ordering, and the ordering of the result may not be wh= at > you expect. To counter this, the documentation of the polymorphic interfa= ce > is careful to precisely define, for functions taking two set arguments, > which of the comparison functions is used in the result set; so the > semantics is maybe-surprising but well-defined. >=20 > On a related note: I believe that a good base library should provide two > separate kinds of modules: concrete modules implementing a particular data > structure (AVL trees, red-black trees, HAMT), and abstract modules build = on > top of it that use whatever implementation is best today to implement > useful interfaces (set, bag, associative map...). > The abstract modules can only be extended with definitions given in terms > of the abstract interface, but concrete modules allow them to easily defi= ne > abstract modules extended with functions relying on the underlying concre= te > data-structure-manipulation primitives. It is a very good design indeed, but OCaml lacks ornaments (or strong enough inlining/specialization, for now) to make this as CPU- and memory-efficient as a specific version. I don't know of a way to write "generic" AVL trees and use them to write Set and Map without paying some cost. Still, exposing the concrete and abstract representation of a specific module (say, stdlib' Set.Make) would be nice indeed. Since there are probably going to be several alternative "standard libraries", do you think OCaml core maintainers would agree to do this for Set, Map and Hashtbl (and maybe also Stack, Queue and Buffer)? It would help alternative/complement stdlibs build on top of the official one, rather than rewriting incompatible types. Personally I'd love to have access to the internals of those modules (especially Buffer). >=20 > Currently with the standard library you only have abstract module, so you > have to re-implement them on your own or break the abstraction boundary in > unsafe ways. >=20 >=20 > On Tue, Sep 29, 2015 at 2:43 PM, S=C3=A9bastien Hinderer < > Sebastien.Hinderer@inria.fr> wrote: >=20 > > Dear all, > > > > Is it possible to implement a polymorphic sets module over the Set > > module provided in OCaml's standard library? > > > > By polymorphic set, I mean a set whose elements could be of type 'a > > (like for lists) and the equality funciton would be the one provided by > > OCaml. > > > > So one would have for instance > > > > val add : 'a -> 'a t -> 'a t > > > > etc. > > > > Is that possible somehow? > > > > Thanks! > > > > S=C3=A9bastien. > > > > -- > > 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 Simon Cruanes http://weusepgp.info/ key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 49AA 62B6 --u3/rZRmxL6MmkK24 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBCAAGBQJWCpOmAAoJEErAHQhJqmK2RAIQAJcqnEFZg/mxQdwaqqBzn1Ex O+2Dqr85x5X6eru+HHvy3QyBMXrZ0J/FF/5oMVjHTaMAX6EAzW04QLb9wtVlalTy v+me+L9bLZqYl00F3xjOdbwi9QbwfzVxv/+FixI4NZwRtdbHwpNOh3beNnzt8hds 6wrjpTrh469N8cI9hP6lTVxqghIQsg6JyqJEUS3lwVH9HVo+fHsD3BWGZZg02DdX QZUbiVzFEXU+5H9y1b8OCK6NulE1e6fQ/qHGRgf89I76QJzz2uroOjEj8Q4CYyNE ksKpbj5xQmqJeYBG9p542w7pssjIBIEtks1ep2PWqL3UeNKdC5t5UFOl3i0no6Kv +CnYzt+qY9PCYnX5NV3PZqoEukB6XW0QIPOI8RleNaN/dRZ1p6g+012JTvx31vG5 eQ0jxAbC7cqbKVh/z5mzy/qlXPzLa5f91CwcYLM0Gvmjy+h45bj965mqF/YODvZA LqNamS9lW9CJ6dglag+BDdZbjFi/m0vPzC77PGe+W4hHBjkDClhzoenO/El314OJ D430jLojYWHt7+eRJuVAm6Be/kVwexPzOVCKTWpRnDpE+DYAi8HAfBUg323vcold jR+TUga9PGThHb5srvgIactc1uyTBNF6WfvkrlCZA3Bjp0ytO+mc0zIwtA4QjL1W 1ZP4j2nrV8GPNpgHIOnM =ebob -----END PGP SIGNATURE----- --u3/rZRmxL6MmkK24--