-------- Original Message --------
Subject: Re: Maps
Date: Tue, 08 Jan 2008 05:35:07 -0800
From: Mike Hamburg
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
interval :: k -> k -> Map k v -> Map k v
(k -> Ordering) -> Map k v -> Map k v
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).
The reason you might not be able to provide the keys yourself is that you can't (efficiently or at all) decide the exact right cutoff value, but you can provide a function that tells whether a key is too high, or too low, or in-range? That makes sense to me. I've even had cases where I wished there was a lookup that didn't require me to convert the key I was trying to look up, into the same type. I guess it would be unsafe though, since then the Map can't guarantee that it's a monotonic function relative to the (compare :: k -> k -> Ordering) that it typically uses -Isaac
Christian Maeder wrote:
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.
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.
If you can specify unbounded ranges like None and All, (a < t < b, All) would do the trick (together with the usual ordering on pairs). You can probably retrofit them on any existing data type that expresses sets/intervals/ranges of values. data Universal r = None | Concrete r | All instance Ranged r => Ranged (Universal r) where range x y = ... union All _ = All ...
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
I assume the O(1) are O(log n) in "reality" but that n < 2^32 because they are machine word integers?
Is there any way to even approach this in Haskell?
Well, the first thing to try is to just use a constructor for between : data Dense = First | Between Dense Dense | Last deriving (Eq) with some clever Ord instance. However, the specification is not complete, what should let half = between a b q1 = between a half q3 = between half b in compare (between q1 q3) half be? If it doesn't matter at all, you can probably use the Stern-Brocot tree http://en.wikipedia.org/wiki/Stern-Brocot_tree i.e. between (a :/ b) (c :/ d) = (a + b) :/ (c + d) with the usual ordering on rational numbers. But you probably won't get the same performance with that: the number of Between constructors or the size in bit of the denominators/numerators grows linearly with the number of between operations. This is unavoidable since there are ~ 2^k values that can be represented with k applications of between . To get better performance, you have drop referential transparency and exploit that only a tiny fraction (namely n ) of these possible 2^k will ever come into existence. Regards, apfelmus
participants (3)
-
apfelmus -
Christian Maeder -
Isaac Dupree