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

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

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.

Reason: removing a set of keys from a map of bindings could be done in
O(n) with a Map.diff function, but only in O(n log n) with the current
functions provided by the Map or Set modules.

An interface for the new functions of PMap could look like this (the
names are not very coherent, but it's just a draft):

(* Shortcuts, just for clarity *)
type ('a, 'b) map = ('a, 'b) t
type 'a set = ('a, unit) map

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

val union : ('a, 'b) map -> (a, 'b) map -> ('a, 'b) map
val key_union : ('a, 'b) map -> ('a, 'c) map -> 'a set

val inter : ('a, 'b) map -> ('a, 'c) map -> ('a, 'b) map
val inter2 : ('a, 'b) map -> ('a, 'c) map -> ('a, ('b, 'c)) map
val key_inter : ('a, 'b) map -> ('a, 'c) map -> 'a set

val key_subset : ('a, 'b) map -> ('a, 'c) map -> bool
val key_equal : ('a, 'b) map -> ('a, 'c) map -> bool

val keys : ('a, 'b) map -> 'a set
val key_set : ('a, 'b) map -> 'a PSet.t
val key_enum : ('a, 'b) map -> 'a Enum.t


Implementation: essentially copy-pasting functions from Set, with minor
modifications.

Is it something that could be added to PMap in ExtLib?
(or in ExtExtLib? :-)


Martin

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