[Fwd: Re: Maps, was Re: GHC source code improvement ideas]
-------- Original Message --------
Subject: Re: Maps, was Re: GHC source code improvement ideas
Date: Fri, 04 Jan 2008 14:38:22 -0800
From: Mike Hamburg
Simon Marlow wrote:
Regarding Data.Map, I'd be interested in trying out AVL trees instead, to see if they have better performance, but then we'd have to import the code of course.
Surely, we want the best maps possible for ghc and as public library (and minimize maintenance).
The problem is to agree on a suitable interface. I would suggest to take (or only slightly change) Daan's interface (the current Data.Map) and improve the underlying implementation possibly using (i.e. Adrian Hey's) AVL trees.
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 or partitionMonotoneWithKey :: (k -> v -> Bool) -> Map k v -> (Map k v, Map k v) or similar. The important thing about these operations is that they can be made to run in O(log n) time if you have the tree structure of the map, and (so far as I know) can't if you don't. An example of when this is useful is if you have a Map (a,b) c, and wish to extract the submap for a particular a-value, or a range of a-values. Mike
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.
participants (2)
-
Christian Maeder -
Paul Johnson