Re: [Caml-list] polymorphic sets?

[Gabriel Scherer <gabriel.scherer@gmail.com>]

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

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

[-- Attachment #2: Type: text/html, Size: 3817 bytes --]