[Haskell-cafe] relational data representation in memory using haskell?

[Isaac Dupree]

Marc Weber wrote:
> On Thu, May 22, 2008 at 03:34:36PM +0200, Marc Weber wrote:
>> On Thu, May 22, 2008 at 09:11:28AM -0400, Isaac Dupree wrote:
>>>  to whoever in this thread hasn't realized it:
>>>  Map String (Map Int Foo) == Map (String,Int) Foo
>>>  (at least to an approximation)
> There is another difference if you want to query <,<=,>,>=
> say String = city and Int = age.
> Now take Map (Int, String) rec and use this index to filter all tuples
> having an age >= 80 and beeing "city"

there are two problems:
Data.Map doesn't have a very good API for that (splitLookup is about the 
best you can get for ranges)
Whether tupled or not, the order of the two indices matters (Int,String) 
vs. (String,Int) for what you can look up efficiently.  It's essentially 
a binary tree either way (Map x (Map y rec)) or (Map (x,y) rec), sorted 
in the same order.  (tuples sort by lexicographical order)

-Isaac