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