[Fwd: Re: Maps, was Re: GHC source code improvement ideas]

[Paul Johnson]

Christian Maeder wrote:
> If anyone is off tweaking the Data.Map library, I have a simple request
> (which I sometimes end up implementing in hacked up versions of
> Data.Map).  There should be some way to extract an implicitly defined
> interval from the map, i.e.
>
> interval :: (k -> v -> Ordering) -> Map k v -> Map k v
>   
I'm not quite sure what you are asking for here.  Why does the first 
argument take both a key and a value, and what is the Ordering saying?  
 From your description I was expecting something more like:

   interval :: k -> k -> Map k v -> Map k v

Are you saying that if the Ordering is "EQ" then the key is within the 
range?

Take a look at my Ranged Sets library (on Hackage) for a complete 
treatment of the concept of ranges within an ordered type.  I can 
imagine something like

   rangedSetMap :: RSet k -> Map k v -> Map k v

where the resulting Map only contains the keys that are in the RSet.  At 
present you would have to do that by iterating through the Map, but I 
can imagine a more efficient method.  Alternatively the Boundary type 
defined in that library might be used: it splits an ordered type into 
values above and below a boundary.  (Two Boundary values make a Range, 
and an ordered list of non-overlapping Ranges is an RSet).

Paul.