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

[Christian Maeder]

-------- Original Message --------
Subject: Re: Maps, was Re: GHC source code improvement ideas
Date: Fri, 04 Jan 2008 14:38:22 -0800
From: Mike Hamburg <mike at mikehamburg.com>
To: Christian Maeder <Christian.Maeder at dfki.de>
References: <477D987C.2090806 at gmail.com> <477E3D69.5000307 at gmail.com>	
<477E5301.8010700 at dfki.de>

On Fri, 2008-01-04 at 16:38 +0100, Christian Maeder wrote:
> 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