[Fwd: Re: Maps]

[Christian Maeder]

-------- Original Message --------
Subject: Re: Maps
Date: Tue, 08 Jan 2008 05:35:07 -0800
From: Mike Hamburg <mike at mikehamburg.com>
To: Christian Maeder <Christian.Maeder at dfki.de>
CC: paul at cogito.org.uk
References: <47832E64.3090008 at dfki.de>

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.  They're derived from
something like a Map t (Map u v), but it is convenient for other reasons
to represent this as an actual Map (t,u) v.  (It's possible that I'll
end up hacking around this with some type class or another, but let's
ignore that possibility for now.)

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.

On Tue, 2008-01-08 at 09:03 +0100, Christian Maeder wrote:
> 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