|Anonymous | Login | Signup for a new account||2017-05-29 02:09 CEST|
|Main | My View | View Issues | Change Log | Roadmap|
|View Issue Details|
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0006138||OCaml||standard library||public||2013-08-25 19:35||2014-01-17 17:56|
|Target Version||Fixed in Version|
|Summary||0006138: Adding a domain function in Map.Make|
|Description||It would be nice to have a domain function in the Map functor, i.e. recovering the set of the keys contained in the map, with the following signature:|
module Make(Ord:OrderedType) :
val domain : 'a t -> Set.Make(Ord).t
which would be essentially identity, except for forgetting the additional node information worn by the map node. That would result in a O(n) operation, while currently one has to do it by hand by using Map.fold and Set.add, resulting in a O(n log n) operation.
Actually, we do this operation quite often in Coq, so that it would be nice to have it built-in more efficiently.
|Additional Information||I made a hackish implementation using unsafe features, and attached it to this message, to see the point.|
|Attached Files||dom.ml [^] (474 bytes) 2013-08-25 19:35 [Show Content]|
This is an interesting suggestion, thanks. What worries me is that even if we put "domain" inside the implementation of Map.Make, we still need unsafe features to build the set of keys -- the type sealing around Set.Make is *that* strong. Or we'd need to duplicate the implementation of Set inside Map...
Yet another way would be for Map.Make to export a substructure (let's call it Keys) that would have the exact same signature as Set.Make(Ord) but be implemented internally as maps. This would make "domain" a constant-time operation.
edited on: 2013-08-28 18:10
What about merging the two functors into a single one? For instance, one could arrange so that Map.Make(Ord) contains a Set submodule, and re-export a Set functor for backward compatibility (with a sharing constraint so that Set.Make(Ord).t = Map.Make(Ord).Set.t).
|2013-08-25 19:35||ppedrot||New Issue|
|2013-08-25 19:35||ppedrot||File Added: dom.ml|
|2013-08-26 17:00||doligez||Status||new => acknowledged|
|2013-08-28 16:08||xleroy||Note Added: 0010252|
|2013-08-28 18:09||frisch||Note Added: 0010255|
|2013-08-28 18:10||frisch||Note Edited: 0010255||View Revisions|
|2014-01-17 17:56||doligez||Tag Attached: patch|
|2017-02-23 16:43||doligez||Category||OCaml standard library => standard library|
|Copyright © 2000 - 2011 MantisBT Group|