# [Fwd: Re: Maps]

apfelmus 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
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

```