Re: [Caml-list] polymorphic sets?

[Simon Cruanes <simon.cruanes.2007@m4x.org>]

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

Le Tue, 29 Sep 2015, Gabriel Scherer a écrit :
> 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.

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).

> 
> 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ébastien 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ébastien.
> >
> > --
> > 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


-- 
Simon Cruanes

http://weusepgp.info/
key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]