[Fwd: Re: Maps]

-------- Original Message -------- Subject: Re: Maps Date: Tue, 08 Jan 2008 05:35:07 -0800 From: Mike Hamburg To: Christian Maeder CC: paul@cogito.org.uk References: <47832E64.3090008@dfki.de> So here's an approximation of my problem. I have a map of objects, possibly aggregated from different sources. They have (in a case of medium complexity) type (t,u) where the t represents the source and u represents the position within that source. They're derived from something like a Map t (Map u v), but it is convenient for other reasons to represent this as an actual Map (t,u) v. (It's possible that I'll end up hacking around this with some type class or another, but let's ignore that possibility for now.) I need to efficiently represent ranges of objects to be viewed or deleted from this map, in such a way that the map library can extract or delete them quickly. But I might have, say, only a t value, and no values of u available. On Tue, 2008-01-08 at 09:03 +0100, Christian Maeder wrote:

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?

Yes. The "ordering" produced is a sort of disjunctive ordering: it's either LT all, or GT all, or EQ at least one element in the interval. I suppose my version should really have type (k -> Ordering) -> Map k v -> Map k v because the values shouldn't come into play unless they're monotonically dependent on the keys.

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

Something like an RSet, with the following operations: union, singleton, Range -> RangeSet, ... upcast :: RangeSet t -> RangeSet (t,u) -- and similar for other product types intersection, difference :: Map k v -> RangeSet k -> 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).

Yes. But I think what you need to efficiently implement this is some sort of implicit cut, of the form (k -> Something) -> Map k v -> (Map k v, Map k v).

Paul.

Also, I'm sort of curious: in C/C++/Java/etc, you can produce a Dense type which has: instance (Eq, Ord, Bounded) Dense between :: Dense -> Dense -> Dense -- if a < b then a < between a b < b This is sort of a lie: between is not referentially transparent, in that two calls to (between a b) may produce results that aren't ==. Still, the efficiency is impressive: ==, >, <, etc are O(1) 'between' is O(log n) where n Dense's are currently live. You can actually make it O(1), but the constant is big, so people don't. total space usage is O(n) integers of 2(log n) bits each Is there any way to even approach this in Haskell? I mean, you can use [Int], but that's not nearly so fast... Mike