Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Sat, 4 Jun 2005, Nicolas Cannasse wrote:

> > Hello,
> >
> > Some useful operations over the keys of a map are not provided by the
> > standard Map module, neither by ExtLib's PMap, but are provided only by
> > the Set module.
>
> Yes I would also love to set  diff / union / intersection for PMaps.
> But I'm not sure which semantic is appropriate.
> Maybe only have diff / union / inter operations on *keys* would be enough ?
> Please fell free to post implementation, maybe based on Set module.

What do you think of this:

(* default merge = fun x y -> x *)
val union : ?merge:('b -> 'b -> 'b) -> ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t

(* a merge function must be given to inter *)
val inter : merge:('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a, 'd) t

val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t

These functions would be quite powerful, I think. The idea is to merge the
values which have the same key during the union and inter operations.
The keys are supposed to be interchangeable like before (in Set or Map) if
the comparison function says they are equal.

So I started the implementation, but it requires the quasi-duplication
and careful adaptation of a lot of code, essentially because the "merge"
arguments are not symmetric in this interface.

For now, only the following works:

val union : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t
val inter : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t
val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t

... where it is not specified which value is kept when 2 bindings have
the same key (union, inter), which is really not that great.

So let me know what you think, before I continue this implementation.

The code is attached to this email. It compiles but was not tested.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr