[Fwd: Re: Maps]
apfelmus at quantentunnel.de
Tue Jan 8 15:09:52 EST 2008
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
with some clever Ord instance. However, the specification is not
complete, what should
half = between a b
q1 = between a half
q3 = between half b
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
More information about the Libraries