-------- 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