[Fwd: Re: Maps]

[apfelmus]

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