[Caml-list] polymorphic sets?

[Caml-list] polymorphic sets?

[Sébastien Hinderer]

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.

Re: [Caml-list] polymorphic sets?

[Gabriel Scherer]

[-- 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 --]

Re: [Caml-list] polymorphic sets?

[Simon Cruanes]

[-- 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 --]

Re: [Caml-list] polymorphic sets?

[Jesper Louis Andersen]

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

On Tue, Sep 29, 2015 at 2:58 PM, Gabriel Scherer <gabriel.scherer@gmail.com>
wrote:

> 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


The only point in time I've had troubles is when you have a map where its
values and keys range over a type that can recursively contain that map of
the same type. This required a polymorphic compare (from Core) to pull off.


-- 
J.

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

Re: [Caml-list] polymorphic sets?

[Yaron Minsky]

Core_kernel's maps and sets solve this problem, and address Gabriel's
concern as well, by providing type witnesses that distinguish maps
built with different comparators.  There's an introduction to the use
of these modules here:

<https://realworldocaml.org/v1/en/html/maps-and-hash-tables.html>

and you can see the current APIs here:

<https://github.com/janestreet/core_kernel/blob/master/src/core_map.mli>

Sets are handled similarly.For sure, better inlining (as is coming in
Flambda!) can make this approach better.

y

On Tue, Sep 29, 2015 at 9:56 AM, Jesper Louis Andersen
<jesper.louis.andersen@gmail.com> wrote:
>
> On Tue, Sep 29, 2015 at 2:58 PM, Gabriel Scherer <gabriel.scherer@gmail.com>
> wrote:
>>
>> 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
>
>
> The only point in time I've had troubles is when you have a map where its
> values and keys range over a type that can recursively contain that map of
> the same type. This required a polymorphic compare (from Core) to pull off.
>
>
> --
> J.

Re: [Caml-list] polymorphic sets?

[Gabriel Scherer]

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

Indeed. With functors one uses the path equality check as a way to enforce
coherence, with a phantom type you can let people build their own phantom
paths and use them to mark type (in)compatibility. This is slightly less
safe (in the sense that users can always break that promise if they want to
by behaving badly -- but I think this is fine), but also easier to use
(than the module language) and more flexible in some cases.

On Tue, Sep 29, 2015 at 4:52 PM, Yaron Minsky <yminsky@janestreet.com>
wrote:

> Core_kernel's maps and sets solve this problem, and address Gabriel's
> concern as well, by providing type witnesses that distinguish maps
> built with different comparators.  There's an introduction to the use
> of these modules here:
>
> <https://realworldocaml.org/v1/en/html/maps-and-hash-tables.html>
>
> and you can see the current APIs here:
>
> <https://github.com/janestreet/core_kernel/blob/master/src/core_map.mli>
>
> Sets are handled similarly.For sure, better inlining (as is coming in
> Flambda!) can make this approach better.
>
> y
>
> On Tue, Sep 29, 2015 at 9:56 AM, Jesper Louis Andersen
> <jesper.louis.andersen@gmail.com> wrote:
> >
> > On Tue, Sep 29, 2015 at 2:58 PM, Gabriel Scherer <
> gabriel.scherer@gmail.com>
> > wrote:
> >>
> >> 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
> >
> >
> > The only point in time I've had troubles is when you have a map where its
> > values and keys range over a type that can recursively contain that map
> of
> > the same type. This required a polymorphic compare (from Core) to pull
> off.
> >
> >
> > --
> > J.
>

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