From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 CC9E47FC54 for ; Tue, 29 Sep 2015 14:59:34 +0200 (CEST) IronPort-PHdr: 9a23:2gUcox3MI+DNS3dPsmDT+DRfVm0co7zxezQtwd8ZsekSI/ad9pjvdHbS+e9qxAeQG96Lt7QZ1KGL4+jJYi8p39WoiDg6aptCVhsI2409vjcLJ4q7M3D9N+PgdCcgHc5PBxdP9nC/NlVJSo6lPwWB6kO74TNaIBjjLw09fr2zQd6OyZnonL3is7ToICx2xxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cYk7sb+sVBSaT3ebgjBfwdVWx+cjMD39DwrRTIUSeI43IdVC1WzksJUED560TB3534qTf7u+xK+CicMcDsQKp8DQ+v5a5wVB7ljmEnNjg1/XvakORxirhaqVSvvUo7i4XdZYXdKeFzZLiVKdgTQG4EWsdKSwRABJm9Zs0BFbxSE/xfqtzSrlEUrBa6TTKnBO71xyUA0nD/17c73uBnCgrG0RYtBfoBtX3VqJP+M6JEArP997XB0TiWN6Ae4jz68oWdN014rA== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=gabriel.scherer@gmail.com; spf=Pass smtp.mailfrom=gabriel.scherer@gmail.com; spf=None smtp.helo=postmaster@mail-io0-f172.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.223.172 as permitted sender) identity=mailfrom; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-io0-f172.google.com) identity=helo; client-ip=209.85.223.172; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-io0-f172.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CFAwAqigpWlKzfVdFdg0M1aQaDJKdbgU6FHIwBgX2FdwKBSwc6EgEBAQEBAQEBEAEBAQEHCwsJHzCCHYIIAQEDARIRBBkBGwsHDAMBCwYFCxodAgIiAREBBQEKEgYBEhIQh3YBAwoIDakFgTA+MYtHgWyCeYoKChknAwpWhDMBAQEHAQEBARgBBQ6GZYN3gQaCboE2ZQuCaYFDBYV9DIw7gzCFFod9gU9GlUCCIxIjgRcRFwuCNIF/PDOJHwEBAQ X-IPAS-Result: A0CFAwAqigpWlKzfVdFdg0M1aQaDJKdbgU6FHIwBgX2FdwKBSwc6EgEBAQEBAQEBEAEBAQEHCwsJHzCCHYIIAQEDARIRBBkBGwsHDAMBCwYFCxodAgIiAREBBQEKEgYBEhIQh3YBAwoIDakFgTA+MYtHgWyCeYoKChknAwpWhDMBAQEHAQEBARgBBQ6GZYN3gQaCboE2ZQuCaYFDBYV9DIw7gzCFFod9gU9GlUCCIxIjgRcRFwuCNIF/PDOJHwEBAQ X-IronPort-AV: E=Sophos;i="5.17,608,1437429600"; d="scan'208";a="179964297" Received: from mail-io0-f172.google.com ([209.85.223.172]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 29 Sep 2015 14:59:33 +0200 Received: by ioii196 with SMTP id i196so9200335ioi.3; Tue, 29 Sep 2015 05:59:32 -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 :content-type; bh=WpyBQPIcreKX1qOuzVjmCMipEX4fNWX3Q+UINSxhRN4=; b=Jplrq753FRQDIMmzD8nPUOpU5H0D+pIJ/j64/RfWSyoJEs/EXSVzFjWEfW3i8NP7uV 2GWIzv/2iQW4ErErtVu1CEasgYWkDisGV0hCw+3XOpcecGaG616WJlbHa9WTPrwQuYOb NlhOs40Ft8olYHb39qQO33f4gih6IzDAa0JneaGHG+B73vUF9f3gAjvPYhEd9Th/8mNN QIFdxUzhcrCXBnJcFdsj6BKeyiRmbCE6W/jGq8UFoQommLiFgAh5STucWxSX1JVlyvkc 5ZO/HhfKEvMIdTYT1FkNyEBf6lK084jy2syRepnidEPzp3eE/vpngJuMeVGLkCGZyP7l gSgA== X-Received: by 10.107.19.70 with SMTP id b67mr23994289ioj.144.1443531572590; Tue, 29 Sep 2015 05:59:32 -0700 (PDT) MIME-Version: 1.0 Received: by 10.79.19.68 with HTTP; Tue, 29 Sep 2015 05:58:53 -0700 (PDT) In-Reply-To: <20150929124344.GA13383@pl-59055.rocqadm.inria.fr> References: <20150929124344.GA13383@pl-59055.rocqadm.inria.fr> From: Gabriel Scherer Date: Tue, 29 Sep 2015 14:58:53 +0200 Message-ID: To: =?UTF-8?Q?S=C3=A9bastien_Hinderer?= , caml users Content-Type: multipart/alternative; boundary=001a113dea229b3bd40520e26291 Subject: Re: [Caml-list] polymorphic sets? --001a113dea229b3bd40520e26291 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable I don't think this is possible. 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: https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/= batSet.ml https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/= batMap.ml 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 what you expect. To counter this, the documentation of the polymorphic interface 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. 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 define abstract modules extended with functions relying on the underlying concrete data-structure-manipulation primitives. 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. On Tue, Sep 29, 2015 at 2:43 PM, S=C3=A9bastien Hinderer < Sebastien.Hinderer@inria.fr> wrote: > 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 > --001a113dea229b3bd40520e26291 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I don't think this is possible.

In Ba= tteries, 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 operatio= n, on top of which both a functorized and a polymorphic interface are built= . You may be interested in the code:

=C2=A0 ht= tps://github.com/ocaml-batteries-team/batteries-included/blob/master/src/ba= tSet.ml
=C2=A0 https://github.com/ocaml-batter= ies-team/batteries-included/blob/master/src/batMap.ml

Note that the polymorphic sets (or maps) are less statically-safe than the= ir functorized counterpart, because they are parametrized over their compar= ison function at creation time (a better choice, I think, that enforcing t= he use polymorphic comparison, think of records with a function parameter f= or example), but then you can mix two sets with same carrier type but diffe= rent ordering, and the ordering of the result may not be what you expect. T= o counter this, the documentation of the polymorphic interface is careful t= o precisely define, for functions taking two set arguments, which of the co= mparison functions is used in the result set; so the semantics is maybe-sur= prising but well-defined.

On a related note: I bel= ieve 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 whatev= er implementation is best today to implement useful interfaces (set, bag, a= ssociative map...).
The abstract modules can only be extended with defin= itions given in terms of the abstract interface, but concrete modules allow= them to easily define abstract modules extended with functions relying on = the underlying concrete data-structure-manipulation primitives.

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.
=C2=A0

=
On Tue, Sep 29, 2015 at 2:43 PM, S=C3=A9bastien = Hinderer <Sebastien.Hinderer@inria.fr> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px= #ccc solid;padding-left:1ex">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.=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

--001a113dea229b3bd40520e26291--