Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006138OCamlOCaml standard librarypublic2013-08-25 19:352014-01-17 17:56
Reporterppedrot 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityN/A
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0006138: Adding a domain function in Map.Make
DescriptionIt 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) :
sig
...
val domain : 'a t -> Set.Make(Ord).t
...
end

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 InformationI made a hackish implementation using unsafe features, and attached it to this message, to see the point.
Tagspatch
Attached Files? file icon dom.ml [^] (474 bytes) 2013-08-25 19:35 [Show Content]

- Relationships

-  Notes
(0010252)
xleroy (administrator)
2013-08-28 16:08

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.
(0010255)
frisch (developer)
2013-08-28 18:09
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).


- Issue History
Date Modified Username Field Change
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


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker